自动搬运

查看原文

来自洛谷，原作者为

	wukaichen888 复健 OI

搬运于2025-08-24 23:16:25，当前版本为作者最后更新于2025-05-21 12:48:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

有个结论：随机排列的严格前缀 $\max$ 数量级为 $O(\log n)$，证明显然。

由于交互器非自适应，考虑初始随机一个区间，随机顺序判断一个点能否更新这个区间（替换区间端点），以保证这个区间含括当前所有已处理点。

先判断当前点是否属于区间，操作 $O(n)$ 次。假如需要更新，再询问一次即可，由上面结论可知这是 $O(\log n)$ 次的。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=50005;
ll n,p[N],s,t;
int main(){
	mt19937 rnd;srand(time(0));rnd.seed(rand());
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) p[i]=i;
	for(ll i=2;i<=n;i++) swap(p[i],p[rand()%(i-1)+1]);
	s=p[1],t=p[2];
	for(ll i=3,x;i<=n;i++){
		printf("? %lld %lld %lld\n",s,t,p[i]);fflush(stdout);scanf("%lld",&x);
		if(x==0){
			printf("? %lld %lld %lld\n",s,p[i],t);fflush(stdout);scanf("%lld",&x);
			if(x) t=p[i]; else s=p[i];
		}
	}
	printf("! %lld %lld\n",s,t);fflush(stdout);
	return 0;
}