#include<bits/stdc++.h>
#define ll long long
using namespace std;
map<string,bool> mp;
ll func(string &a,char ch,bool front,ll n){
ll l=0;
ll h=n-a.length();
ll fin=0;
while(l<=h){
ll mid=(l+h)/2;
if(mid==0){
l=mid+1;
continue;
}
string s;
string g="";
if(front)
s=a+g.append(mid,ch);
else
s=g.append(mid,ch)+a;
for(auto i:mp){
if(!i.second&&s.find(i.first)!=std::string::npos){
return 0;
}
}
cout<<"? "<<s<<endl;
cout.flush();
ll ans;
cin>>ans;
mp[s]=ans;
cout.flush();
if(ans) {
l=mid+1;
fin=mid;
}
else h=mid-1;
}
return fin;
}
void solve(){
mp.clear();
ll n;
cin>>n;
assert(n != -1);
cout.flush();
bool ones=0;
bool zeros=0;
ll res;
cout<<"? 0"<<endl;
cout.flush();
cin>>res;
cout.flush();
zeros=res;
string a;
if(zeros){
a="0";
cout<<"? 01"<<endl;
cout.flush();
cin>>res;
cout.flush();
if(res){
a="01";
} else {
cout<<"? 10"<<endl;
cout.flush();
cin>>res;
cout.flush();
if(res) a="10";
}
}
if(a.length()==1){
string s="";
cout<<s.append(n,'0');
cout.flush();
return;
} else if(a.length()==0){
cout<<"? 1"<<endl;
cout.flush();
cin>>res;
cout.flush();
if(res){
a="1";
}
}
// cout.flush();
// ones=res;
// if(!zeros&&ones){
// string s="";
// cout<<s.append(n,'1');
// cout.flush();
// return;
// } else if(!ones&&zeros){
// }
if(a=="1"){
ll l=1;
ll h=n;
ll ans=0;
a="1";
while(l<=h){
ll mid=(l+h)/2;
string s=a;
s.append(mid,'1');
cout<<"? "<<s<<endl;
cout.flush();
cin>>ans;
cout.flush();
// cout<<ans<<" "<<a<<endl;
if(!ans) h=mid-1;
else {
l=mid+1;
a=s;
}
}
}
// cout<<"asdasd\n";
bool peeche=1;
bool aage=1;
while(a.length()!=n){
string e="",f="",g="",h="";
if(aage){
ll nxtZer=func(a,'0',1,n);
if(nxtZer) a+=g.append(nxtZer,'0'),aage=1;
ll nxtOnes=0;
if(nxtZer==0) nxtOnes=func(a,'1',1,n);
if(nxtOnes) a+=h.append(nxtOnes,'1'),aage=1;
if(!nxtOnes&&!nxtZer) aage=0;
}
if(peeche){
ll prevZer=func(a,'0',0,n);
if(prevZer) a=e.append(prevZer,'0')+a,peeche=1;
ll prevOnes=0;
if(prevZer==0) prevOnes=func(a,'1',0,n);
if(prevOnes) a=f.append(prevOnes,'1')+a,peeche=1;
if(!prevOnes&&!prevZer) peeche=0;
}
}
cout<<"! "<<a<<endl;
cout.flush();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll t;
cin>>t;
cout.flush();
while(t--){
solve();
}
return 0;
}
Compilation message
dna.cpp: In function 'void solve()':
dna.cpp:120:21: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
120 | while(a.length()!=n){
| ~~~~~~~~~~^~~
dna.cpp:46:10: warning: unused variable 'ones' [-Wunused-variable]
46 | bool ones=0;
| ^~~~
grader.cpp: In function 'bool make_test(std::string)':
grader.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; i < p.size(); i++) {
| ~~^~~~~~~~~~
grader.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for (int i = 1; i <= ss.size(); i++) {
| ~~^~~~~~~~~~~~
grader.cpp:28:13: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | if (pr[i] == p.size()) {
/usr/bin/ld: /tmp/ccpoPrUp.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc8IYXNs.o:dna.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccpoPrUp.o: in function `main':
grader.cpp:(.text.startup+0x4e): undefined reference to `analyse[abi:cxx11](int, int)'
collect2: error: ld returned 1 exit status
