Codeforces Round #580 DIV1 C問題/DIV2 E問題 - Palindromic Paths

Source

Codeforces Round #580 DIV1 C問題 (1250pt)
Codeforces Round #580 DIV2 E問題 (2250pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20190820-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int N;
int res[50][50];

int query(int x1, int y1, int x2, int y2){
  int r;
  sortE(x1, x2);
  sortE(y1, y2);
  printf("? %d %d %d %d\n",x1+1,y1+1,x2+1,y2+1);
  fflush(stdout);
  scanf("%d",&r);
  return r;
}

int match(int a, int b, int m){
  sortE(a,b);
  if(a==b) return 1;
  if(m==0){
    if(a==0 && b==2) return 1;
    if(a==1 && b==3) return 1;
  } else {
    if(a==1 && b==2) return 1;
    if(a==0 && b==3) return 1;
  }
  return 0;
}

pair<int,int> pre_query(int x1, int y1, int x2, int y2){
  int i, j, k, s;
  int val[4];
  pair<int,int> r = make_pair(0,0);
  
  sortE(x1, x2);
  sortE(y1, y2);

  rep(k,1<<3){
    i = x1;
    j = y1;
    val[0] = res[i][j];
    rep(s,3){
      if(k&1<<s) i++;
      else       j++;
      if(i >= N || j >= N) break;
      val[s+1] = res[i][j];
    }
    if(i==x2 && j==y2){
      if(match(val[0],val[3],0) && match(val[1],val[2],0)) r.first = 1;
      if(match(val[0],val[3],1) && match(val[1],val[2],1)) r.second = 1;
    }
  }

  return r;
}

void answer(void){
  int i, j;
  puts("!");
  rep(i,N){
    rep(j,N) printf("%d",res[i][j]);
    puts("");
  }
  fflush(stdout);
}

{
  int i, j, k;
  int si, sj, ni, nj;
  int di[4] = {1,-1,2,0}, dj[4] = {1,-1,0,2}, d;
  int st[10000], sts;
  pair<int,int> p;
  scanf("%d", &N);

  rep(i,N) rep(j,N) res[i][j] = -1;
  res[0][0] = 1;
  res[N-1][N-1] = 0;

  for(i=2;i<N;i+=2){
    k = query(0, i-2, 0, i);
    res[0][i] = (res[0][i-2] ^ k ^ 1);
    k = query(i-2, 0, i, 0);
    res[i][0] = (res[i-2][0] ^ k ^ 1);
  }
  rep(i,1,N) rep(j,1,N) if( (i+j)%2==0 && i+j != 2N-2 ){
    k = query(i-1, j-1, i, j);
    res[i][j] = (res[i-1][j-1] ^ k ^ 1);
  }

  res[0][1] = 2;
  sts = 0;
  st[sts++] = 1;
  while(sts){
    k = st[--sts];
    si = k / N;
    sj = k % N;
    rep(d,4){
      ni = si + di[d];
      nj = sj + dj[d];
      if(ni < 0 || nj < 0 || ni >= N || nj >= N || res[ni][nj] != -1) continue;
      i = query(si, sj, ni, nj);
      res[ni][nj] = (res[si][sj] ^ i ^ 1);
      st[sts++] = ni * N + nj;
    }
  }

  rep(si,N) rep(sj,N) rep(k,4){
    ni = si + k;
    nj = sj + (3 - k);
    if(ni >= N || nj >= N) continue;
    p = pre_query(si, sj, ni, nj);
    if(p.first != p.second){
      d = query(si, sj, ni, nj);
      if(p.first == d){
        rep(i,N) rep(j,N){
          if(res[i][j] == 2) res[i][j] = 0;
          if(res[i][j] == 3) res[i][j] = 1;
        }
      } else {
        rep(i,N) rep(j,N){
          if(res[i][j] == 2) res[i][j] = 1;
          if(res[i][j] == 3) res[i][j] = 0;
        }
      }
    }
  }

  answer();
}

Current time: 2024年05月09日01時12分41秒
Last modified: 2019年08月21日05時10分19秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF580 CF_Div1_C CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)