交互题好玩
首先,可以通过 次异或询问(具体实现是询问 与 异或后的结果)来求出整个序列两两之间的异或关系,并且在求出一个位置的具体数值之后直接得到整个序列,于是还剩下 次询问。
考虑任意的三个数 (代码中取 ),我们已经通过之前的 次询问知道了它们两两之间异或的结果。考虑这三个数的第 位,分别记为 ( ),有 种可能情况:,,,。对于每一种情况,只要知道两个相等的位(如第二种情况中的 和 ) 的值就可以求出 。
于是,分别询问 ,, 即可在 次操作内得到序列。
// 2020.11.21
// Code by LTb
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2<<17;
int n;
int a[MAXN];
signed main()
{
cin>>n;
for (int i=2;i<=n;i++){
cout<<"XOR 1 "<<i<<endl;
cin>>a[i];
}
int x,y,z;
cout<<"AND 1 2"<<endl;
cin>>x;
cout<<"AND 1 3"<<endl;
cin>>y;
cout<<"AND 2 3"<<endl;
cin>>z;
int qwq=a[2]^a[3],ans=0;
for (int i=15;i>=0;i--){
int tmp1=(x>>i)&1,tmp2=(y>>i)&1,tmp3=(z>>i)&1;
int tmp4=(a[2]>>i)&1,tmp5=(a[3]>>i)&1,tmp6=(qwq>>i)&1;
if ((!tmp4) && (!tmp5) && (!tmp6)){
ans|=tmp1<<i;
}
else{
if (!tmp4) ans|=tmp1<<i;
else if (!tmp5) ans|=tmp2<<i;
else ans|=(!tmp3)<<i;
}
}
cout<<"! "<<ans;
for (int i=2;i<=n;i++)
cout<<' '<<(ans^a[i]);
cout<<endl;
return 0;
}