原題鏈接

分享圖片

解析

首先小心不要把“總跳躍次數”看成“總跳躍長度”。

如果你做過前一場的 E，那么你應該很快能想到要把 \(\lceil \frac{3n}{2} \rceil\) 變成 \(n + \lceil \frac{n}{2} \rceil\)。

手玩一下，發現如果設 \(s_i\) 表示從 \(i\) 開始跳的總跳躍次數，當 \(s_{i + 1} \not= s_{i + 2}\) 時，可以通過 \(\texttt{throw } i\) 確定 \(a_i\) 和 \(s_i\) 的值；而當 \(s_{i + 1} = s_{i + 2}\) 時，雖然無法直接確定 \(a_i\) 的值，但是可以得知 \(s_i = s_{i + 1} + 1\)。

這樣掃一遍過后，在任意相鄰的 \(3\) 個位置上，\(s\) 至少有 \(2\) 種不同的取值。這也意味著對于任意相鄰的兩個位置，未知的 \(a\) 至多有 \(1\) 個。

太好了，這不就跟 \(\lceil \frac{n}{2} \rceil\) 對上了嘛。于是我們來嘗試在兩次操作以內求出一個未知的 \(a\)。對于一個位置 \(i\)，如果 \(a_i\) 是未知的，那么有 \(s_{i + 1} = s_{i + 2}\) 且 \(a_{i + 1} = 2\)。利用這個性質，只需先 \(\texttt{swap } i\) 再 \(\texttt{throw } i+1\)，若得到 \(s_{i + 1}\)，則說明 \(a_i=2\)，否則 \(a_i=1\)。正著掃一遍就可以求出除 \(a_n\) 外所有的值。

求 \(a_n\) 的方法想必你已經手玩出來了，這里不多贅述。

代碼

由于我第二次是倒著掃的，所以還要維護交換后的 \(s\) 和 \(a\)，并且需要處理交換導致的對于一個 \(a\) 未知的位置 \(s_{i + 1} \not= s_{i + 2}\) 的情況，換個順序進行操作可以規避這些問題。

/*
*/
#include<bits/stdc++.h>
#define eps 0.000001
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<ll,int> pii;
const int N = 2e5 + 5,M = 3.2e4 + 5;
ll a[N],stp[N],val[N],vis[N];
int main(){
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);
//	ios::sync_with_stdio(false);
//	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		stp[n] = 1;
		int x;
		cout<<"throw "<<n - 1<<endl;
		cin>>x;
		a[n - 1] = x ^ 3;
		cout<<"swap "<<n - 1<<endl;
		cout<<"throw "<<n - 1<<endl;
		cin>>x;
		a[n] = x ^ 3;
		val[n - 1] = a[n],val[n] = a[n - 1];
		stp[n - 1] = x;
		stp[n + 1] = 0;
		for(int i=n - 2;i>=1;i--){
			if(stp[i + 1] != stp[i + 2] && stp[i + 2]){
				int x;
				cout<<"throw "<<i<<endl;
				cin>>x;
				stp[i] = x;
				if(x == stp[i + 2] + 1) a[i] = 2;
				else a[i] = 1;
				val[i] = a[i];
			}else{
				stp[i] = stp[i + 1] + 1;
			}
		}
		for(int i=n - 2;i>=1;i--){
			if(!a[i]){
				if(stp[i + 1] != stp[i + 2]){
					int x;
					cout<<"throw "<<i<<endl;
					cin>>x;
					stp[i] = x;
					if(x == stp[i + 2] + 1) a[i] = 2;
					else a[i] = 1;
					val[i] = a[i];
					continue;
				}
				int x,y;
				x = stp[i + 1];		
				cout<<"swap "<<i<<endl;
				cout<<"throw "<<i + 1<<endl;
				cin>>y;
				val[i] = val[i + 1];
				val[i + 1] = a[i] = y == x ? 2 : 1;
				stp[i + 1] = y;
				stp[i] = stp[i + val[i]] + 1;
			}else{
				stp[i] = stp[i + a[i]] + 1;
			}
		}
		cout<<"! "; 
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" ";
			a[i] = stp[i] = val[i] = 0;
		}
		cout<<endl;
	} 
	return 0;
}
/*
*/