【题解】CF1451E2

也许你应该在阅读这篇题解之前读一读 E1的题解

限制从 $n+2$ 减少到了 $n+1$，于是考虑把 $3$ 次 $\operatorname{AND}$ 操作减少至 $2$ 次。

注意到，如果原序列中存在两个相等的数，在它们之前做一次 $\operatorname{AND}$ 询问就可以简单地得出它们的值。

若不存在，因为有 $a_i \in [0,n-1]$，所以原序列是 $0 \sim n-1$ 的一个排列。我们考虑使取到的 $b,c$（$b,c$ 同E1题解中的定义） 满足 $b \operatorname{AND} c = 0$，这样 $b,c$ 不会在任何一位产生相等，可以少询问一次 $b \operatorname{AND} c$。

// 2020.11.22
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN=2<<17;
int n;
int a[MAXN];
int ap[MAXN];

signed main()

{
	cin>>n;
	int xx=0,yy=0,zz;
	ap[0]=1;
	for (int i=2;i<=n;i++){
		cout<<"XOR 1 "<<i<<endl;
		cin>>a[i];
		if (ap[a[i]] && !xx){ // 此时 a[ap[a[i]]] 与 a[i] 相等
			yy=ap[a[i]];
			xx=i;
		}
		ap[a[i]]=i;
	}

	if (!xx){ // 若不存在相等的数
		xx=1;
		zz=0;
		for (int i=2;i<=n;i++){
			if (a[i]==n-2) yy=i;
			else if (a[i]==1) zz=i; //随便钦定两个数使它们AND值为0
		}
	}
	else{ // 若存在相等的数
		for (int i=1;i<=n;i++)
			if (i!=xx && i!=yy) zz=i;
	}

	int x,y,z;
	cout<<"AND "<<xx<<' '<<yy<<endl;
	cin>>x;
	cout<<"AND "<<xx<<' '<<zz<<endl;
	cin>>y;

	int qwq=a[2]^a[3],ans=0;
	for (int i=15;i>=0;i--){
		int tmp1=(x>>i)&1,tmp2=(y>>i)&1;
		int tmp4=((a[xx]^a[yy])>>i)&1,tmp5=((a[xx]^a[zz])>>i)&1,tmp6=((a[yy]^a[zz])>>i)&1;
		if ((!tmp4) && (!tmp5) && (!tmp6)){
			ans|=tmp1<<i;
		}
		else{
			if (!tmp4) ans|=tmp1<<i;
			else ans|=tmp2<<i;
		}
	}

	cout<<"! "<<(ans^a[xx]);
	for (int i=2;i<=n;i++){
		cout<<' '<<(ans^a[i]^a[xx]);
	}
	cout<<endl;
	return 0;
}