Submission #1363662

#TimeUsernameProblemLanguageResultExecution timeMemory
1363662husseinjuandaDark Ride (EGOI25_darkride)C++20
9 / 100
0 ms352 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){
    int mid = (l+r)/2;
    if(query.size() == level){
        query.push_back({});
    }
    for(int i = l; i <= mid; i++){
        query[level].push_back(i);
    }
    if(l == r) return;
    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;
    }
    if(ns[level] == 1){
        if(fns <= mid){
            fo(mid+1, r, level+1);
        }else{
            fo(l, mid, level+1);
        }
    }else{
        if(fns <= mid){
            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 = 0;
    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 fns
    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...