Codeforces Global Round 5 H問題 - Balanced Reversals

Source

Codeforces Global Round 5 H問題 (4000pt)
Problem description

問題概要

省略

解法

省略

cLayversion 20191108-1)のコード

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

//no-unlocked
int N; char S[4002], T[4002];
int A[2000], B[2000];

int fn[2000], sz;
int cnt[4];
int ress, res[8002];

void doit(int k){
  res[ress++] = k;
  reverse(A, A+k);
  rep(i,k) if[A[i]==1, A[i]++, A[i]==2, A[i]--];
}

void doit(int a, int b, int c = -1){
  doit(a); doit(b);
  if(c != -1) doit(c);
}

{
  int r, mx;
  Rand rnd;
  REP(rd_int()){
    rd(S@N, T);
    N /= 2;
    rep(i,4) cnt[i] = 0;
    rep(i,2N) S[i] -= '0', T[i] -= '0';
    rep(i,N) A[i] = S[2i]*2 + S[2i+1];
    rep(i,N) B[i] = T[2i]*2 + T[2i+1];
    rep(i,N) cnt[A[i]]++, cnt[B[i]]--;
    if(cnt[0] || cnt[3]) wt(-1), continue;
    for(;;){
      ress = 0;
      r = N;
      rep(i,N) A[i] = S[2i]*2 + S[2i+1];
      rep(i,N) B[i] = T[2i]*2 + T[2i+1];
      while(r){
        if(A[r-1] == B[r-1]) r--, continue;

        sz = mx = 0;
        rep(i,r) rep(k,i+1){
          if(A[i-k] != B[r-1-k]) break;
          if(mx > k+1) continue;
          if(mx < k+1) mx = k+1, sz = 0;
          fn[sz++] = i;
        }
        if(mx <= 2 && ((A[0]==1 && B[r-1]==2)||(A[0]==2 && B[r-1]==1))) doit(r), continue;
        if(sz) doit(fn[rnd.get(sz)]+1, r), continue;

        sz = 0;
        rep(i,r) if(A[i] == 3-B[r-1]) fn[sz++] = i;
        doit(fn[rnd.get(sz)]+1, 1, r), continue;
      }
      if(ress <= 2N+1) break;
    }
    wt(ress);
    wt(res(ress)*2);
  }
}

Current time: 2021年12月06日00時10分15秒
Last modified: 2019年11月10日19時11分46秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_5
トップページに戻る

Logged in as: unknown user (not login)

ログイン: