제출 #1357749

#제출 시각아이디문제언어결과실행 시간메모리
1357749sallyDark Ride (EGOI25_darkride)C++20
55 / 100
1 ms664 KiB
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
int N;
typedef pair<int,int> pii;
int cnt = 1;
int guess(vector<int>& group, int l, int r) {
    string s(N, '0');
    for(int i=l; i<=r; i++) s[group[i]] = '1';
    cout<<"? "<<s<<endl;
    int res;
    cin>>res;
    return res;
}
int main() {
    cin>>N;
    int split_bit;
    // 兩個數字至少有一個bit是不一樣的,只要找出這個bit,就可以把兩個數字分到兩群
    // 枚舉每個bit,把有這個bit的分成一群
    for(int i=0; (1<<i)<N; i++) { // 15次
        vector<int> group;
        for(int j=0; j<N; j++) {
            if((j>>i)&1) group.push_back(j);
        }
        int res = guess(group, 0, group.size()-1);
        if(res&1) {
            split_bit = i;
            break;
        }
    }
    vector<int> g1,g2;
    for(int i=0; i<N; i++) {
        if((i>>split_bit)&1) g1.push_back(i);
        else g2.push_back(i);
    }
    int l=0, r=g1.size()-1;
    while(l<r) {
        int mid = (l+r)/2;
        int res = guess(g1, l, mid);
        if(res&1) {
            r = mid;
        }
        else {
            l = mid+1;
        }
    }
    int L=0, R = g2.size()-1;
    while(L<R) {
        int mid = (L+R)/2;
        int res = guess(g2, L, mid);
        if(res&1) {
            R = mid;
        }
        else {
            L = mid+1;
        }
    }
    cout<<"! "<<g1[l]<<' '<<g2[L]<<endl;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…