AtCoder Beginner Contest 164 F問題 - I hate Matrix Construction

Source

AtCoder Beginner Contest 164
問題文

問題概要

省略

解法

省略

cLayversion 20200430-1)のコード

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

int N;
int S[500], T[500];
ull U[500], V[500];

ull res[500][500];

int rtyp[500], ctyp[500], rval[500], cval[500];
int tmp[500][500];
int fs, f[500];

int solve(int bt){
  int r0 = 0, r1 = 0, c0 = 0, c1 = 0;
  int x, y, cx, cy, iy;

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

  rep(i,N){
    rtyp[i] = S[i];
    ctyp[i] = T[i];
    rval[i] = (U[i] >> bt) & 1;
    cval[i] = (V[i] >> bt) & 1;
  }

  rep(i,N) if(rtyp[i]==0 && rval[i]==1){
    rep(j,N) if(tmp[i][j]==0) return 0;
    rep(j,N) tmp[i][j] = 1;
    r1 = 1;
  }
  rep(i,N) if(rtyp[i]==1 && rval[i]==0){
    rep(j,N) if(tmp[i][j]==1) return 0;
    rep(j,N) tmp[i][j] = 0;
    r0 = 1;
  }

  rep(i,N) if(ctyp[i]==0 && cval[i]==1){
    rep(j,N) if(tmp[i][j]==0) return 0;
    rep(j,N) tmp[j][i] = 1;
    c1 = 1;
  }
  rep(i,N) if(ctyp[i]==1 && cval[i]==0){
    rep(j,N) if(tmp[j][i]==1) return 0;
    rep(j,N) tmp[j][i] = 0;
    c0 = 1;
  }

//  wt(bt,r0,r1,c0,c1);

  if(r0+r1==1 && c0+c1==0){
    cx = cy = 0;
    rep(i,N) if[rval[i]==0, cx, cy]++;
    if(cx && cy) r0 = r1 = 1;
  }
  if(r0+r1==0 && c0+c1==1){
    cx = cy = 0;
    rep(i,N) if[cval[i]==0, cx, cy]++;
    if(cx && cy) c0 = c1 = 1;
  }

  if(r0 && c0){
    rep(i,N) rep(j,N) if(tmp[i][j]==-1) tmp[i][j] = 1;
  } else if(r1 && c1) {
    rep(i,N) rep(j,N) if(tmp[i][j]==-1) tmp[i][j] = 0;
  } else if(r0 && r1) {
    rep(i,N) rep(j,N) tmp[i][j] = rval[i];
  } else if(c0 && c1) {
    rep(i,N) rep(j,N) tmp[i][j] = cval[j];
  } else if(r0 || r1) {
    x = if[r0, 0, 1];
    y = 1 - x;

    cx = cy = 0;
    rep(i,N) if[cval[i]==x, cx, cy]++;

    fs = 0;
    rep(i,N) if(rtyp[i]==rval[i]) f[fs++] = i;

    if(cx){
      rep(i,N) rep(j,N) if(tmp[i][j]==-1) tmp[i][j] = cval[j];
    } else if(fs >= 2) {
      rep(i,N) rep(j,N) tmp[i][j] = x;
      rep(i,N) tmp[f[i%2]][i] = y;
    } else {
      return 0;
    }
  } else if(c0 || c1) {
    x = if[c0, 0, 1];
    y = 1 - x;

    cx = cy = 0;
    rep(i,N) if[rval[i]==x, cx, cy]++;

    fs = 0;
    rep(i,N) if(ctyp[i]==cval[i]) f[fs++] = i;

    if(cx){
      rep(i,N) rep(j,N) if(tmp[i][j]==-1) tmp[i][j] = rval[i];
    } else if(fs >= 2) {
      rep(i,N) rep(j,N) tmp[i][j] = x;
      rep(i,N) tmp[i][f[i%2]] = y;
    } else {
      return 0;
    }
  } else {
    if(N==1){
      if(rval[0] != cval[0]) return 0;
      tmp[0][0] = rval[0];
    } else {
      rep(i,N) rep(j,N) tmp[i][j] = (i+j) % 2;
    }
  }

  rep(i,N) rep(j,N) if(tmp[i][j]==1) res[i][j] |= (1ULL << bt);
  return 1;
}

{
  rd(N,S(N),T(N),U(N),V(N));
  rep(i,64) if(!solve(i)) wt(-1), return 0;
  wt(res(N,N));
}

Current time: 2021年09月18日05時03分10秒
Last modified: 2020年04月30日03時23分22秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC164 ABC_F
トップページに戻る

Logged in as: unknown user (not login)

ログイン: