Codeforces Global Round 5 H問題 (4000pt)
Problem description
省略
省略
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: 2024年03月29日06時27分50秒
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)