これは賢い。
https://yukicoder.me/problems/no/1959
問題
1~Nの順列Pを特定するインタラクティブ問題である。
0/1で構成され長さN-1の数列Aを指定すると、下記数列Bが返る。
このクエリを10回まで用いて、Pを特定せよ。
- B[0]=P[0]
- B[i+1]=max(B[i],P[i]) (A[i]==0の場合)
- B[i+1]=min(B[i],P[i]) (A[i]==1の場合)
解法
B[i]!=B[i+1]の場合B[i+1]=P[i]となる。
この状態を作るには、A=(0,1,0,1,...)と(1,0,1,0,....)と2種類のクエリを投げれば、各添え字について、いずれかの返り値でB[i]!=B[i+1]となるBが得られる。
int T,N; int A[1010],B[1010],C[1010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N; cout<<"?"; FOR(i,N-1) { cout<<" "<<(i%2); } cout<<endl; FOR(i,N) cin>>A[i]; cout<<"?"; FOR(i,N-1) { cout<<" "<<((i%2)^1); } cout<<endl; FOR(i,N) cin>>B[i]; C[0]=A[0]; for(i=1;i<N;i++) { if(A[i]!=A[i-1]) C[i]=A[i]; if(B[i]!=B[i-1]) C[i]=B[i]; } cout<<"!"; FOR(i,N) cout<<" "<<C[i]; cout<<endl; } }
まとめ
クエリ回数がO(logN)ぐらいかかるように見えて、O(1)というのがいいね。