Submission #1357949

#TimeUsernameProblemLanguageResultExecution timeMemory
1357949sallyDark Ride (EGOI25_darkride)C++20
17 / 100
1 ms568 KiB
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
int N;
typedef pair<int,int> pii;
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分群,如果一樣就會是even,不一樣就會是odd,只要找出第一個就可以知道另一個是誰了
    vector<bool> same(20, false);
    // 枚舉每個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;
            same[i] = 0; // 不一樣
        }
        else same[i] = 1; // 一樣
    }
    vector<int> g1;
    for(int i=0; i<N; i++) {
        if((i>>split_bit)&1) g1.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 ans1 = g1[l], ans2 = 0;
    for(int i=0; (1<<i)<=ans1; i++) {
        int x = (ans1>>i)&1;
        ans2>>=1;
        if(same[i]) ans2+=x;
        else ans2 += (x+1)%2;
    }
    cout<<"! "<<ans1<<' '<<ans2<<endl;
}
#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...