Codeforces Global Round 3 C問題 (1500pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, P[3d5];
int inv[3d5];
int M, A[15d5], B[15d5];
void swap_sub(int a, int b){
swap(P[a], P[b]);
swap(inv[P[a]], inv[P[b]]);
A[M] = a+1;
B[M++] = b+1;
}
void swap_main(int a, int b){
if(a > b) swap(a,b);
if(b-a >= N/2){
swap_sub(a,b);
return;
}
if( a >= N/2 && b >= N/2 ){
swap_sub(0,a);
swap_sub(0,b);
swap_sub(0,a);
return;
}
if( N-1-a >= N/2 && N-1-b >= N/2 ){
swap_sub(N-1,a);
swap_sub(N-1,b);
swap_sub(N-1,a);
return;
}
swap_sub(0, b);
swap_sub(a, N-1);
swap_sub(0, N-1);
swap_sub(0, b);
swap_sub(a, N-1);
}
{
int i, j, k;
rd(N,P(N));
rep(i,N) P[i]--;
rep(i,N) inv[P[i]] = i;
rep(i,N) if(P[i]!=i){
swap_main(i, inv[i]);
}
wt(M);
rep(i,M) wt(A[i],B[i]);
}
Current time: 2024年04月19日20時38分18秒
Last modified: 2019年06月02日04時30分35秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_3
トップページに戻る
Logged in as: unknown user (not login)