Codeforces Global Round 13 : F. Magnets

また妙にややこしい設定の問題。
https://codeforces.com/contest/1491/problem/F

問題

N個の磁石があり、それぞれ以下の属性のいずれかである。

• Nである
• Sである
• いずれでもない

3つ目の属性の磁石をすべて当てるinteractive問題である。
1回のクエリでは、磁石をいくつか選び、2つのグループに分けることができる。
N1,N2,S1,S2を、それぞれのグループに割り当てられたN,Sの磁石の個数とする。
その際、N1*N2+S1*S2-N1*S2-N2*S1の値が返る。ただし、その値の絶対値がNを超えてはならない。

N+logN回以下のクエリ呼び出し回数で、3つ目の属性の磁石を列挙せよ。

解法

片方のグループを、1要素に固定すればクエリの帰り値の絶対値はNを超えない。

まず、磁石のうち2つ目のNまたはSの要素を求めよう。
これは、片方のグループにi、もう片方のグループに[0,i)を指定すれば、初めて非0となったiが2つ目のNまたはSの要素である。
以降の磁石jに関しては、iとjを両グループに指定すれば、jの属性が確定する。

あとは、[0,i)の範囲で1つ目のNまたはSの要素を求める必要があるが、これは二分探索をすればよい。

int T,N;
int R[2020];

int ask(int a,int L,int R) {
	cout<<"? 1 "<<(R-L+1)<<endl;
	cout<<a<<endl;
	int i;
	for(i=L;i<=R;i++) cout<<i<<" ";
	cout<<endl;
	cin>>i;
	return i;
}

vector<int> hoge() {
	int i;
	
	int tar=-1;
	ZERO(R);
	for(i=2;i<=N;i++) {
		if(tar==-1) {
			R[i]=ask(i,1,i-1);
			if(R[i]) tar=i;
		}
		else {
			R[i]=ask(i,tar,tar);
		}
	}
	int A=1,B=tar;
	while(A+1<B) {
		int M=(A+B)/2;
		if(ask(tar,A,M-1)) {
			B=M;
		}
		else {
			A=M;
		}
	}
	R[A]=1;
	
	
	vector<int> cand;
	for(i=1;i<=N;i++) if(R[i]==0) cand.push_back(i);
	return cand;
	
	
	
}

まとめ

2つ目の要素をまず探すってアプローチが珍しいね。