Codeforces Global Round 23 : E2. Joking (Hard Version)

本番Hardは解けず。
https://codeforces.com/contest/1746/problem/E2

問題

1～Nの範囲の整数Xを当てるinteractive問題である。
以下の2種類のクエリを使いXを特定せよ。

• 整数集合Sを与えると、XがSに含まれるかどうか答える。
• Xとなる整数を指定する。

後者は2回まで利用できる。
前者は53回まで利用できる。ただし、回答が嘘であることがある。とはいえ2回連続嘘をつくことはない。

解法

今特定したい整数集合をVとする。
最後のクエリの内容をA、V-AをBとする。
AからとBから半分ずつ選んでクエリを投げることで、クエリ毎に3/4ずつ候補を絞ることができる。

int N;
int T[4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> A,B;
	FOR(i,N) A.push_back(i+1);
	while(A.size()+B.size()>2) {
		int a1=min(A.size(),A.size()/2+B.size()%2);
		int b1=B.size()/2;
		int c=a1+b1;
		cout<<"? "<<c<<endl;
		FOR(i,a1) cout<<A[i]<<" ";
		FOR(i,b1) cout<<B[i]<<" ";
		cout<<endl;
		cin>>s;
		vector<int> PA=A,PB=B;
		A.clear(),B.clear();
		if(s=="YES") {
			FOR(i,PA.size()) {
				if(i<a1) A.push_back(PA[i]);
				else B.push_back(PA[i]);
			}
			FOR(i,b1) A.push_back(PB[i]);
		}
		else {
			FOR(i,PA.size()) {
				if(i<a1) B.push_back(PA[i]);
				else A.push_back(PA[i]);
			}
			for(i=b1;i<PB.size();i++) A.push_back(PB[i]);
		}
	}
	FORR(b,B) A.push_back(b);
	
	cout<<"! "<<A[0]<<endl;
	cin>>s;
	if(s==":(") {
		cout<<"! "<<A[1]<<endl;
		cin>>s;
		assert(s==":)");
	}
	
	
}

まとめ

回数から多少推測つくかもしれないけど、一発で回答にたどり着くのはしんどいな。