Submission #1363668

#TimeUsernameProblemLanguageResultExecution timeMemory
1363668husseinjuandaDark Ride (EGOI25_darkride)C++20
100 / 100
3 ms2708 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<int>> query;
vector<int> ns;

void t(int l, int r, int level){
    if(l == r) return;
    int mid = (l+r)/2;
    if(query.size() == level){
        query.push_back({});
    }
    for(int i = l; i <= mid; i++){
        query[level].push_back(i);
    }
    t(l, mid, level+1);
    t(mid+1, r, level+1);
}

int fns = 0;
int other;

void fo(int l, int r, int level){
    int mid = (l+r)/2;
    if(l == r){
        other = l;
        return;
    }
    bool ada = false;
    for(auto i : query[level]){
        if(i == fns){
            ada = true;
        }
    }
    if(ns[level]%2 == 1){
        if(ada){
            fo(mid+1, r, level+1);
        }else{
            fo(l, mid, level+1);
        }
    }else{
        if(ada){
            fo(l, mid, level+1);
        }else{
            fo(mid+1, r, level+1);
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    t(1, n, 0);
    ns.resize(query.size());
    int it = -1;
    string j = "";
    for(int i = 0; i < n; i++){
        j += '0';
    }
    for(int i = 0; i < query.size(); i++){
        string q = j;
        for(auto y : query[i]){
            q[y-1] = '1';
        }
        cout << "? " << q << endl;
        int w; cin >> w;
        if(w%2 == 1){
            it = i;
        }
        ns[i] = w;
    }
    int low = 0;
    int top = query[it].size()-1;
    // for(auto i : query[it]){
    //     cout << i << endl;
    // }
    while(low <= top){
        int mid = (low + top)/2;
        string a = j;
        for(int i = 0; i <= mid; i++){
            a[query[it][i]-1] = '1';
        }
        cout << "? " << a << endl;
        int w; cin >> w;
        // cout << mid << " " << w << "AJJAJAJ" << endl;
        if(w%2 == 1){
            top = mid-1;
            fns = mid;
        }else{
            low = mid+1;
        }
    }
    fns = query[it][fns];
    //first one is in ns
    fo(1, n, 0);
    cout << "! " << fns-1 << " " << other-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...