[[interactive]] [[Divide and Conquer]]
link
We are allowed to query 15 times, and n<1000.
Obviously, use divide and conquer algorithm.
A small conclusion
Make \(h(1,n)\) represent the Hamming distance from 1 to n.
x is the number before altering, y is after.
We change 0/1 within the range of 1~mid.
\[\begin{cases} &x=h(1,n)=h(1,m)+h(m+1,r)\\ &y=h'(1,m)+h(m+1,r)=(m-l+1-h(1,m))+h(m+1,r)\\ \end{cases} \\ \iff \\ \begin{cases} &h(l,m)=(x-y-(m-l+1))/2\\ &h(m+1,r)=(x+y+(m-l+1))/2 \end{cases} \]Then, we can use \(h1[2]\), \(h2[2]\) to represent the number of number 0 or 1 in two sides.
If one side is full of 1 or full of 0. The next goal is to find the another number in the other side.
If both sides have 1 and 0, choose either side to continue to divide and conquer.
#include<bits/stdc++.h>
using namespace std;
int n,o[1003],h1[2],h2[2],x[2],y,h;
void print(){
printf("? ");
for(int i=1;i<=n;i++)printf("%d",o[i]);
printf("\n");
fflush(stdout);
}
int ans[2];
void end(){
printf("! %d %d",ans[0],ans[1]);
exit(0);
}
void to1(int f){
x[0]=h1[0],x[1]=h1[1];
h+=h2[f];
}
void to2(int f){
x[0]=h2[0],x[1]=h2[1];
h+=h1[f^1];
}
void dc(int l,int r,int f){
int m=l+r>>1;
for(int i=l;i<=m;i++)o[i]=f;
print();scanf("%d",&y);
y-=h;
h1[f]=(x[f]-y+(m-l+1))/2;//the number of f
h1[f^1]=m-l+1-h1[f];
h2[f]=(x[f]+y-(m-l+1))/2;
h2[f^1]=r-m-h2[f];
if(!ans[0]&&!ans[1]){
if(h1[f]==m-l+1||h1[f]==0){
if(h1[f]==m-l+1)ans[f]=l;
if(h1[f]==0)ans[f^1]=l;
to2(f);dc(m+1,r,f);
}
else{
if(h2[f]==r-m)ans[f]=r;
if(h2[f]==0)ans[f^1]=r;
to1(f);dc(l,m,f^1);
}
return;
}
for(int i=0;i<=1;i++)if(!ans[i]){
if(h1[i]==m-l+1)ans[i]=l,end();
if(h2[i]==r-m)ans[i]=r,end();
if(!h1[i])to2(f),dc(m+1,r,f);
else to1(f),dc(l,m,f^1);
return;
}
}
int main(){
scanf("%d",&n);
print();
scanf("%d",&x[1]);x[0]=n-x[1];
dc(1,n,1);
}