Submission #1361253

#TimeUsernameProblemLanguageResultExecution timeMemory
1361253yyc000123Dark Ride (EGOI25_darkride)C++20
71 / 100
2 ms728 KiB
#include<bits/stdc++.h>
using namespace std ;
const int N = 3e4+5 ;
int n , arr[N] , ans[2] ;
vector<int> v[2] ;

bool query(int t , int le , int ri){
    string s = "" ;
    for(int i=0 ; i<n ; i++) s+='0' ;
    for(int i=le ; i<=ri ; i++) s[v[t][i]]='1' ;
    cout << "? " << s << endl ;
    int k ; cin >> k ;
    return (k&1) ;
}

void randf(int level , int le , int ri , int t=-1){
    if(!level){
        for(int i=le ; i<=ri ; i++) v[t].push_back(i) ;
        return ;
    }
    int mi = (le+ri)/2 ;
    randf(level-1,le,mi,1) ; randf(level-1,mi+1,ri,0) ;
}

void f(int t , int le , int ri){
    if(le==ri){ ans[t]=v[t][le] ; return ; }
    else if(ri-le==1){
        bool temp = query(t,le,le) ;
        if(temp) ans[t]=v[t][le] ;
        else ans[t]=v[t][ri] ;
        return ;
    }
    int mi = (le+ri)/2 ;
    bool temp = query(t,le,mi) ;
    if(temp) f(t,le,mi) ;
    else f(t,mi+1,ri) ;
}

int main(){
    cin >> n ;
    if(n<=30){
        int t = 0 ;
        for(int i=0 ; i<n ; i++){
            v[0].push_back(i) ;
            if(query(0,0,0)) ans[t]=i , t++ ;
            v[0].pop_back() ;
        }
        cout << "! " << ans[0] << ' ' << ans[1] << endl ;
        return 0 ;
    }
    else{
        for(int i=0 ; i<n/2 ; i++) v[0].push_back(i) ;
        for(int i=n/2 ; i<n ; i++) v[1].push_back(i) ;
        if(!query(0,0,(int)v[0].size()-1)){
            v[0].clear() ; v[1].clear() ;
            v[0].push_back(0) ;
            for(int i=1 ; i<n ; i++){
                v[1].push_back(i) ;
            }
            int temp = 1 ;
            while(!query(0,0,(int)v[0].size()-1)){
                v[0].clear() ; v[1].clear() ;
                randf(temp,0,n-1) ; temp++ ;
            }
        }
    }
    f(0,0,(int)v[0].size()-1) ; f(1,0,(int)v[1].size()-1) ;
    cout << "! " << ans[0] << ' ' << ans[1] << endl ;
    return 0 ;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...