제출 #1361435

#제출 시각아이디문제언어결과실행 시간메모리
1361435yyc000123Dark Ride (EGOI25_darkride)C++20
100 / 100
2 ms640 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) ;
}

void f1(int level , int le , int ri , int a){
    if(!level){
        v[1].clear() ;
        for(int i=le ; i<=ri ; i++) v[1].push_back(i) ;
        f(1,0,(int)v[1].size()-1) ;
        return ;
    }
    int mi = (le+ri)/2 ;
    if(level==1){
        if(le<=a && a<=mi) f1(level-1,mi+1,ri,a) ;
        else f1(level-1,le,mi,a) ;
    }
    else if(le<=a && a<=mi) f1(level-1,le,mi,a) ;
    else f1(level-1,mi+1,ri,a) ;
}

int main(){
    cin >> n ;
    int temp = 0 ;
    do{
        v[0].clear() ; v[1].clear() ;
        temp++ ; randf(temp,0,n-1) ;
    }while(!query(0,0,(int)v[0].size()-1)) ;
    f(0,0,(int)v[0].size()-1) ;
    // f(1,0,(int)v[1].size()-1) ;
    f1(temp,0,n-1,ans[0]) ;
    cout << "! " << ans[0] << ' ' << ans[1] << endl ;
    return 0 ;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…