Codeforces Round 978(div.2) D1

#感觉挺有意思的一道题

题目:

思路:

观察发现对于两个人a,b如果两个人里面没有Impostor那么,你得到的回答是一样的,如果有impostor那么结果不同,那么我们就可以两个两个的询问,先找到2个人里面有impostor然后在找另外一个人来询问就行了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
void solve(){
	int n;cin>>n;
	int a=1,b=2;
	while(1){
		int t1,t2;
		cout<<"? "<<a<<" "<<b<<endl;
		cout.flush();
		cin>>t1;
		cout<<"? "<<b<<" "<<a<<endl;
		cout.flush();
		cin>>t2;
		if(t1!=t2){
			break;
		}
		a+=2;
		b+=2;
		if(b>n){
			cout<<"! "<<n<<endl;
			cout.flush();
			return;
		}
	}
	int t=b+1;
	if(t>n)t%=n;
	int t1,t2;
	cout<<"? "<<t<<" "<<a<<endl;
	cout.flush();
	cin>>t1;
	cout<<"? "<<a<<" "<<t<<endl;
	cout.flush();
	cin>>t2;
	if(t1==t2){
		cout<<"! "<<b<<endl;
		cout.flush();
		return;
	}else{
		cout<<"! "<<a<<endl;
		cout.flush();
		return;
	}
	return;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;cin>>_;
	while(_--)solve();
	return 0;
}