Submission #1333874

#TimeUsernameProblemLanguageResultExecution timeMemory
1333874eri16Dark Ride (EGOI25_darkride)C++20
100 / 100
6 ms544 KiB
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

ll n,t;

ll query(string s){
    
    string q;
    
    for (int i=0; i<n; i++){
        
        ll correct = 1;
        
        for (int j=0; j<15; j++){
        
            if (s[j]=='2'){continue;}
            
            else if (s[j]=='0' && !((1<<j) & i)){continue;}
            else if (s[j]=='1' && ((1<<j) & i)){continue;}        
            else{correct = 0;}
        }
        
        if (correct){q.push_back('1');}
        else{q.push_back('0');}
        
    }
    
    cout<<"? "<<q<<endl;
    cin>>t;
    return t;
}


int main(){
    
    cin>>n;
    
    string s;
    
    for (int i=0; i<15; i++){
        s.push_back('2');
    }   
    
    string xor_bits;
    ll z=0;
    
    for (int i=0; i<15; i++){
        s[i]='1';
        ll k = query(s);
        s[i]='2';
        if (k%2==0){xor_bits.push_back('0');}
        if (k%2==1){xor_bits.push_back('1');z=i;}
    }

    ll xor_val=0;
    for (int i=0; i<15; i++){if (xor_bits[i] == '1') xor_val |= (1 << i);}
    
    //cout<<xor_val<<"\n";
    
    vector<int> idx;
    for (int i=0; i<n; i++){if ((i >> z) & 1) idx.push_back(i);}
    
    int l=0, r=(int)idx.size()-1;
    
    //for (auto x : idx){cout<<x<<' ';}
    
    string ss;
    
    for (int i=0; i<n; i++){ss.push_back('0');}
    
    while (l<r){
        int mid=(l+r)/2;
        fill(ss.begin(), ss.end(), '0');

        for (int k=l; k<=mid; k++){
            ss[idx[k]]='1';
        }
        
        cout<<"? "<<ss<<endl;
        ll res;
        cin>>res;

        if (res%2==1){r=mid;}
        else{l=mid+1;}
    }

    int first=idx[l];
    int second=first^xor_val;

    cout<<"! "<<first<<" "<<second<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...