Codeforces Round #599 DIV1 C問題/DIV2 E問題 - Sum Balance

Source

Codeforces Round #599 DIV1 C問題 (1500pt)
Codeforces Round #599 DIV2 E問題 (2500pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20191110-1)のコード

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

//no-unlocked
int K;
int N[15]; ll A[15][5000], ss[15];

map<ll,int> box;
int ok[32768], val[32768][15], go[32768][15];
int tval[15], tgo[15];

{
  int i, j, k, bt, all, c, cn, dm;
  ll sm = 0, v, nx;
  rd(K);
  rep(i,K) rd(N[i], A[i](N[i]));
  rep(i,K) rep(j,N[i]) box[A[i][j]] = i;
  rep(i,K) rep(j,N[i]) ss[i] += A[i][j];

  sm = sum(ss(K));
  if(sm % K) wt("No"), return 0;
  sm /= K;

  rep(i,K) rep(j,N[i]){
    c = i;
    bt = BIT_ith(i);
    v = A[i][j];
    dm = 0;
    for(;;){
      nx = sm - ss[c] + v;
      if(box.count(nx)==0) dm = 1, break;
      cn = box[nx];
      tval[c] = v;
      tgo[cn] = c;
      if(cn == i){
        if(nx != A[i][j]) dm = 1;
        break;
      }
      if(BIT_ith(bt, cn)) dm = 1, break;
      v = nx;
      c = cn;
      bt |= BIT_ith(c);
    }
    if(dm) continue;

    if(ok[bt]) continue;
    ok[bt] = 1;
    rep(m,K) val[bt][m] = tval[m], go[bt][m] = tgo[m];
  }

  rep(i,1<<K) if(!ok[i]){
    for(j=((i-1)&i);j;j=((j-1)&i)){
      k = i^j;
      if(!ok[j] || !ok[k]) continue;
      ok[i] = 1;
      rep(x,K) if(BIT_ith(i,x)){
        if(BIT_ith(j,x)) val[i][x] = val[j][x], go[i][x] = go[j][x];
        if(BIT_ith(k,x)) val[i][x] = val[k][x], go[i][x] = go[k][x];
      }
      break;
    }
  }

  all = (1<<K) - 1;

  if(!ok[all]) wt("No"), return 0;
  wt("Yes");
  rep(i,K) wt(val[all][i], go[all][i]+1);
}

Current time: 2021年11月30日21時11分29秒
Last modified: 2019年11月10日22時37分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF599 CF_Div1_C CF_Div2_E
トップページに戻る

Logged in as: unknown user (not login)

ログイン: