Codeforces #1068 : Div2. E. Shiro's Mirror Duel

こういう問題、一回ドツボに入るとなかなか直らない…。
https://codeforces.com/contest/2173/problem/E

問題

1～NのPermutation Pが与えられる。
これを以下の手順を2.5N+800回以下で、昇順に揃えるinteractive問題である。

１回のクエリでは、２要素P[x],P[y]を指定する。
そうすると、P[x]とP[y]またはP[N-1-x]とP[N-1-y]のどちらかの組を1/2の確率でswapする。

解法

Nが奇数の場合、(N+1)/2が真ん中に車でクエリを連打しよう。
あとはPを両側とも外側から合わせて行く。
R[i] は、P[R[i]]=iとなる値とする。

P[i] == i と P[N-1-i] == N-1-iの少なくとも片側が満たされない場合、以下を繰り返す。

• P[i]!=iなら、P[i]とP[R[i]]を指定
• P[N-1-i]!=N-1-iなら、P[N-1-i]とP[R[N-1-i]]を指定

上記を繰り返すと、期待値としては４回以内にP[i]とP[N-1-i]が正しい場所に来る。

int T;
int N;
int P[4040],R[4040],M[4040];

void ask(int a,int b) {
	cout<<"? "<<a+1<<" "<<b+1<<endl;
	cin>>a>>b;
	a--,b--;
	swap(P[a],P[b]);
	R[P[a]]=a;
	R[P[b]]=b;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>P[i];
			P[i]--;
			R[P[i]]=i;
			M[i]=N-1-i;
		}
		if(N%2) {
			while(P[N/2]!=N/2) ask(R[N/2],N/2);
		}
		FOR(i,N/2) {
			while(P[i]!=i||P[M[i]]!=M[i]) {
				if(P[i]!=i) ask(i,R[i]);
				else ask(M[i],R[M[i]]);
			}
		}
		cout<<"!"<<endl;
	}
			
}

まとめ

これは本番解いておきたかったな。