Codeforces #922 : Div2 E. Counting Binary Strings

7問回。
https://codeforces.com/contest/1918/problem/E

問題

1～NのPermutation Aを答えるinteractive問題である。
初期状態で変数Xがあるが、その値は1～Nのいずれか知らされない。

クエリとして1要素を選び、A[i]とXの大小関係を答えさせることができる。
ただし、A[i]がXより大きい場合、クエリ後Xが1増え、A[i]がXより小さい場合、クエリ後Xが1減ってしまう。
クエリ回数40N以下で、Aの各要素を特定せよ。

解法

まず全要素を2周し、最大要素と最小要素を特定しよう。
前者は、順に要素を見て行ってXが大きくできる限り大きくしていくことを繰り返せばよい。

あとはクイックソートの要領で処理する。
区間内の最小値A[L]と最大値A[R]があるとする。クエリでLやRを連打すれば、A[L]とA[R]の中間値A[M]がわかる。
次に、対応するMを全要素走査して探せばよい。

あとは、各要素A[M]以上か以下かで分類し、再帰的に処理すればよい。

int T,N;
int ma,mi;
int S[2020];
int tcur=0;
int V[2020]={2,4,1,5,3};

int ask(int v) {
	string s;
	cout<<"? "<<v+1<<endl;
	if(tcur) {
		if(V[v]>tcur) {
			s=">";
			tcur++;
		}
		else if(V[v]<tcur) {
			s="<";
			tcur--;
		}
		else {
			s="=";
		}
	}
	else {
		cin>>s;
	}
	if(s==">") return 1;
	if(s=="<") return -1;
	return 0;
}
int dfs(int cur,int L,int R,vector<int> V) {
	if(L>R) return cur;
	int M=(L+R)/2;
	vector<int> A,B;
	while(cur<M) ask(ma), cur++;
	while(cur>M) ask(mi), cur--;
	FORR(v,V) {
		int ret=ask(v);
		if(ret==0) {
			S[v]=M;
		}
		else if(ret==1) {
			B.push_back(v);
			ask(mi);
		}
		else {
			A.push_back(v);
			ask(ma);
		}
	}
	cur=dfs(cur,L,M-1,A);
	cur=dfs(cur,M+1,R,B);
	return cur;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ma=-1,mi=-1;
		FOR(i,N) {
			x=ask(i);
			if(x==-1) {
				if(ma!=-1) ask(ma);
			}
			else if(x==0) {
				if(ma==-1) ma=i;
			}
			else {
				while(1) {
					x=ask(i);
					if(x==0) break;
				}
				ma=i;
			}
		}
		FOR(i,N) {
			x=ask(i);
			if(x==1) {
				if(mi!=-1) ask(mi);
			}
			else if(x==0) {
				if(mi==-1) mi=i;
			}
			else {
				while(1) {
					x=ask(i);
					if(x==0) break;
				}
				mi=i;
			}
		}
		S[mi]=1;
		S[ma]=N;
		vector<int> V;
		FOR(i,N) ask(mi);
		FOR(i,N) if(i!=mi&&i!=ma) V.push_back(i);
		dfs(1,2,N-1,V);
		cout<<"!";
		FOR(i,N) cout<<" "<<S[i];
		cout<<endl;
	}
}

まとめ

結構本番手間取ってるな…。