Google Code Jam 2021 Round 2 : A. Minimum Sort

無事通過できてよかった。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000435915/00000000007dc51c

問題

それぞれdistictな値を持つ100要素の数列がある。
この値は明示的には与えられない。
以下のクエリを使い、この配列を昇順に並べたい。

• 区間を指定すると、最小値を持つ要素を返す。その際、区間長Lに対しceil(10^8/L)のコストがかかる。
• 任意の2要素をswapする。

総コストを6*10^8以下に抑えて、配列を並べ替えよ。

解法

なので、i番目の要素を決めるときには[i,100]の区間にクエリを発行し、最小要素をi番目とswapすればよい。

int N;

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	ll ret=0;
	
	for(i=1;i<N;i++) {
		cout<<"M "<<i<<" "<<N<<endl;
		cin>>x;
		if(i!=x) {
			cout<<"S "<<i<<" "<<x<<endl;
			cin>>x;
			assert(x==1);
		}
	}
	
	cout<<"D"<<endl;
	cin>>x;
	assert(x==1);
}

まとめ

本番、15ptもあるのでもう少しややこしいかと思ったのだが、コストの総和を計算したら拍子抜けした。