Submission #1360807

#TimeUsernameProblemLanguageResultExecution timeMemory
1360807yyc000123Dark Ride (EGOI25_darkride)C++20
24 / 100
7 ms636 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) ;
}

bool randf(){
    v[0].clear() ; v[1].clear() ;
    srand(time(0)) ;
    for(int i=0 ; i<n ; i++){
        v[rand()%2].push_back(i) ;
    }
    if(v[0].empty() || v[1].empty()) return randf() ;
    return query(0,0,v[0].size()-1) ;
}

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 while(!randf()) ;
    cout << "! " << 0 << ' ' << 1 << endl ; return 0 ; //
    f(0,0,v[0].size()-1) ; f(1,0,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...