| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1091580 | indresh | Martian DNA (IOI16_dna) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}