Codeforces Round #704 DIV2 E問題 - Almost Fault-Tolerant Database

Source

Codeforces Round #704 DIV2 E問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20210223-1）のコード

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

//no-unlocked
int N, M, **A;
int res[3d5], ng[];
{
  int mx, mxi, ind[4], chk;
  rd(N,M);
  walloc2d(&A,N,M);
  rd(A(N,M));
  rep(i,N) ng[i] = HammingDistance(M, A[0], A[i]);
  mx = max(ng(N));
  if(mx > 4) wt("No"), return 0;
  if(mx <= 2) wt("Yes"), wt(A[0](M)), return 0;

  (mx, mxi) = (0, argmax(ng(N)));
  rep(i,M) if(A[0][i] != A[mxi][i]) ind[mx++] = i;
  rep(i,N) rep(j,mx) if(A[0][ind[j]] != A[i][ind[j]]) ng[i]--;
  rep(i,M) res[i] = A[0][i];

  if(mx==3){
    rep(x,mx) rep(y,mx) if(x!=y){
      (res[ind[x]], res[ind[y]]) = (A[0][ind[x]], A[mxi][ind[y]]);
      rep(i,N){
        chk = ng[i];
        if(res[ind[x]] != A[i][ind[x]]) chk++;
        if(res[ind[y]] != A[i][ind[y]]) chk++;
        if(chk == 2) res[ind[3-x-y]] = A[i][ind[3-x-y]];
      }
      if(max[i,0,N](HammingDistance(M,res,A[i])) > 2) continue;
      wt("Yes"), wt(res(M)), return 0;
    }
  } else {
    rep(x,mx) rep(y,x+1,mx){
      rep(i,4) res[ind[i]] = A[0][ind[i]];
      (res[ind[x]], res[ind[y]]) = (A[mxi][ind[x]], A[mxi][ind[y]]);
      if(max[i,0,N](HammingDistance(M,res,A[i])) > 2) continue;
      wt("Yes"), wt(res(M)), return 0;
    }
  }
  wt("No");
}

Current time: 2024年04月23日22時45分32秒
Last modified: 2021年02月24日08時17分58秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF704 CF_DIV2_E
トップページに戻る

Logged in as: unknown user (not login)