注意到题目中精明精灵的数量不小于糊涂精灵的数量，那我们随机取 $20$ 个精灵至少会有一个精灵是精明精灵的概率会超级接近 $1$。

那如何检查一个精灵是否是精明精灵呢，只需要让他重复检查另一个精灵然后看结果是否有不同的就行了。

但是极限数据有 $\frac{1}{1000}$ 的概率才会返回不同的结果，所以我们重复问 $5000$ 次，就只有 $0.999^{5000}=0.006$ 的概率糊涂精灵才会返回完全相同的结果。

然后就做完了，随机化就是神。

#include<bits/stdc++.h>
#include "smart.h"
using namespace std;
const int N=5e4;
mt19937 rnd(time(0));
void init(int c,int t){}
bool check(int x)
{
	int y=x==1?2:1,pre=0;
	for(int i=1;i<=N;i++)
	{
		int now=query(x,y);
		if(i!=1&&now!=pre)return 0;
		pre=now;
	}
	return 1;
}
int smart(int n,int x,int y)
{
	for(int i=1;i<=20;i++)
	{
		int id=rnd()%n+1;
		if(check(id))return id;
	}
	return rnd()%n+1;
}