Codeforces #1045 : Div2. E. Power Boxes

なんか変わった解き味だった。
https://codeforces.com/contest/2134/problem/E

問題

N要素の整数列Aを当てるinteractive問題である。
Aの各要素は1,2のいずれかである。

以下のクエリを3N/2回まで用いてAを特定せよ。

• xを指定し、A[x]とA[x+1]をswapする。
• xを指定する。するとx=x+A[x]という作業をxがNを超えるまで繰り返し、その回数を答える。

解法

A[x]を大きい順に確定させる。
f(x) := 2つ目のクエリの値
とする。

• f(x+1)!=f(x+2)の場合、後者のクエリによりA[x]が1か2か確定できる。
• そうでない場合、A[x+1]=2が確定することを利用し、A[x]とA[x+1]をswapして(swap後の)A[x+1]の阿多を求める。

int T,N;

int A[202020];
int dp[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N+3) dp[i]=0;
		
		vector<int> S={N-1};
		cout<<"throw "<<N-1<<endl;
		cin>>dp[N];
		if(dp[N]==2) A[N]=1;
		else A[N]=2;
		dp[N]=1;
		cout<<"swap "<<N-1<<endl;
		
		for(i=N-1;i>=1;i--) {
			if(dp[i+1]!=dp[i+2]) {
				cout<<"throw "<<i<<endl;
				cin>>dp[i];
				if(dp[i]==dp[i+1]+1) A[i]=1;
				else A[i]=2;
			}
			else if(i==1) {
				cout<<"swap "<<i<<endl;
				swap(A[i],A[i+1]);
				assert(A[i]==2);
				assert(dp[i+2]!=dp[i+3]);
				S.push_back(i);
				cout<<"throw "<<i+1<<endl;
				cin>>dp[i+1];
				if(dp[i+1]==dp[i+2]+1) A[i+1]=1;
				else A[i+1]=2;
				dp[i]=dp[i+A[i]]+1;
			}
			else {
				i--;
				cout<<"throw "<<i<<endl;
				cin>>dp[i];
				if(dp[i]==dp[i+2]+1) A[i]=2;
				else A[i]=1;
				cout<<"swap "<<i<<endl;
				S.push_back(i);
				swap(A[i],A[i+1]);
				dp[i+1]=dp[i+2]+1;
				assert(dp[i+1]!=dp[i+2]);
				i++;
			}
		}
		
		reverse(ALL(S));
		FORR(s,S) swap(A[s],A[s+1]);
		
		
		cout<<"!";
		for(i=1;i<=N;i++) cout<<" "<<A[i];
		cout<<endl;
	}
}

まとめ

本番結構苦戦したな…。