Google Code Jam 2021 Qualification Round : D. Median Sort

これはなかなか面白かった。
https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d1284

問題

互いに異なる値を持つN要素の数列Xがある。
この要素番号を昇順または降順に並べるinteractive問題である。

クエリとして、3つの要素を指定するとそのMedianが返されるものが利用できる。
N=50の時、170回以下のクエリで大小順を特定せよ。

解法

まず1回クエリを実行し、先頭3要素を並べよう。
真ん中さえ正しければ、両端はどちらがどちらでもよい。

以降、4要素目以降を順次ここに挿入していく。
この時、三分探索を用いる。
今p要素目まで確定済みで、その並び順がY[0]...Y[p-1]で現れるとする。
L=-1, R=pから初めて三分探索で絞り込んでいこう。
LとRの間を3等分する2要素と、挿入したい要素を含むクエリを投げると、挿入したい要素が3等分した領域のどこに入るかがわかるので、クエリ1回で挿入位置を1/3に絞り込める。

int T,N,Q;

int ask(int i,int j,int k) {
	cout<<i<<" "<<j<<" "<<k<<endl;
	cin>>i;
	return i;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	vector<int> V;
	x=ask(1,2,3);
	if(x==1) V={2,1,3};
	else if(x==2) V={1,2,3};
	else if(x==3) V={1,3,2};
	
	for(i=4;i<=N;i++) {
		int L=-1;
		int R=V.size();
		while(R-L>1) {
			if(R-L==2) {
				int M=(R+L)/2;
				if(L!=-1) {
					x=ask(V[L],V[M],i);
					assert(x!=V[L]);
					if(x==i) {
						R=M;
					}
					else {
						L=M;
					}
				}
				else {
					x=ask(V[M],V[R],i);
					assert(x!=V[R]);
					if(x==i) {
						L=M;
					}
					else {
						R=M;
					}
				}
			}
			else {
				int M1=(R+L*2)/3;
				int M2=(R*2+L)/3;
				x=ask(V[M1],V[M2],i);
				if(x==V[M1]) {
					R=M1;
				}
				else if(x==V[M2]) {
					L=M2;
				}
				else {
					L=M1,R=M2;
				}
			}
		}
		V.insert(V.begin()+L+1,i);
	}
	
	
	FOR(i,N) {
		cout<<V[i];
		if(i!=N-1) cout<<" ";
	}
	cout<<endl;
	cin>>x;
	assert(x==1);
	
}

まとめ

CodeforcesのDiv2とかで出そうな問題。