제출 #1357703

#제출 시각아이디문제언어결과실행 시간메모리
1357703sallyDark Ride (EGOI25_darkride)C++20
0 / 100
0 ms344 KiB
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
int N;
typedef pair<int,int> pii;
int guess(int l, int r) {
    cout<<"? ";
    for(int i=0; i<N; i++) {
        if(l<=i && i<=r) cout<<1;
        else cout<<0;
    }
    cout<<endl;
    int res;
    cin>>res;
    return res;
}
int main() {
    cin>>N;
    vector<int> ans;
    queue<pii> even, odd;
    if(guess(0, (N-1)/2)%2 == 0) even.push( {0, (N-1) / 2} );
    else odd.push({0, (N-1)/2});
    if(guess((N-1)/2+1, N-1)%2 == 0) even.push({(N-1)/2+1, N-1});
    else odd.push({(N-1)/2+1, N-1});
    while(odd.size()<2 && even.size()) {
        auto [l, r] = even.front();
        even.pop();
        int mid = (l + r)/2;
        int res1 = guess(l, mid);
        if(res1&1) odd.push({l, mid});
        else if(odd.size()==0) even.push({l, mid}); // 如果odd已經有一個了,那代表兩個不在同一塊,就只要再找一個odd的
        if(odd.size()==2) break;
        int res2 = guess(mid+1, r);
        if(res2&1) odd.push({mid+1, r});
        else if(odd.size()==0) even.push({mid+1, r});
    }
    int L = odd.front().first, R = odd.front().second;
    odd.pop();
    int l = odd.front().first, r = odd.front().second;
    while(L<R) {
        int mid = (L+R)/2;
        int res1 = guess(L, mid);
        if(res1%2) {
            R = mid;
        }
        else {
            L = mid+1;
        }
    }
    while(l<r) {
        int mid = (l+r)/2;
        int res1 = guess(l, mid);
        if(res1%2) {
            r = mid;
        }
        else {
            l = mid+1;
        }
    }
    cout<<l<<' '<<L<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…