【CF1364E】X-OR

题目

题目链接：https://codeforces.com/problemset/problem/1364/E
本题是交互题。
有一个固定的长度为 (n) 的排列 (P)，其值域为 ([0,n-1])，你可以进行不超过 (4269) 次询问，之后你需要输出这个排列 (P)。
你可以按照 ? a b 的格式进行询问，之后你会得到 (P_a) 与 (P_b) 的按位或。
当你需要输出 (P) 时，首先输出一个 !，之后输出 (n) 个整数 (P_i)。
(3leq nleq 2048)。

思路

我们只需要找出 (0)，然后就可以再进行 (n-1) 次询问确定每一个元素。
假设我们有两个 (0) 的候选位置 (a,b)，考虑一个之前没有枚举过的 (c)：

• 如果 (a ext{ or } b<b ext{ or } c)，因为 (x ext{ or } ygeq max(x,y))，所以 (c) 一定不可能是 (0)。
• 如果 (a ext{ or } b>b ext{ or } c)，同理 (a) 一定不是 (0)，用 (c) 代替 (a)。
• 如果 (a ext{ or } b=b ext{ or }c)，那么 (b) 一定不是 (0)，用 (c) 代替 (b)。

最后我们就可以得到 (0) 元素的两个候选位置 (a,b)。然后不断随机一个位置 (c)，如果 (a ext{ or }c eq b ext{ or }c)，那么小的那一边就是 (0)。
在两个候选位置得到正确的 (0) 时，考虑那一个非零的元素，最坏情况下它只有一位是 (1)，而我们期望 (2) 次就可以随机到一个这一位是 (0) 的数字。所以这一步的期望次数仅仅为 (2)，需要的询问数为 (4)。
至于在最开始的一步中，如果用 (c) 代替 (b)，那么就需要多一次的询问。这个 CF 官方题解也没有证明期望下的次数。但是感性理解一下这种情况出现概率其实很少。
所以最后期望操作次数为 (2n+4+k)。非常不严谨 /kk。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=2050;
int n,a,b,c,d,ans[N],p[N];

int print(int x,int y)
{
	printf("? %d %d
",x,y); fflush(stdout);
	scanf("%d",&x);
	return x;
}

int main()
{
	srand(7777777);
	scanf("%d",&n);
	for (int i=1;i<=n;i++) p[i]=i;
	random_shuffle(p+1,p+1+n);
	a=p[1]; b=p[2]; c=print(a,b);
	for (int i=3;i<=n;i++)
	{
		d=print(a,p[i]);
		if (c>d) b=p[i],c=d;
		else if (c==d) a=p[i],c=print(a,b);
	}
	while (1)
	{
		int x=(rand()*32768+rand())%n+1;
		while (x==a || x==b) x=(rand()*32768+rand())%n+1;
		c=print(a,x); d=print(b,x);
		if (c<d) break;
		if (c>d) { a=b; break; }
	}
	for (int i=1;i<=n;i++)
		if (i!=a) ans[i]=print(a,i);
	printf("!");
	for (int i=1;i<=n;i++)
		printf(" %d",ans[i]);
	printf("
"); fflush(stdout);
	return 0;
}