Submission #1334085

#TimeUsernameProblemLanguageResultExecution timeMemory
1334085SpyrosAlivDark Ride (EGOI25_darkride)C++20
71 / 100
30 ms652 KiB
#include <bits/stdc++.h>
using namespace std;

const int MN = 3e4+5;

int n;
bool isOn[MN];

int ask() {
    cout << "? ";
    for (int i = 1; i <= n; i++) {
        cout << isOn[i];
    }
    cout << endl;
    int ret; cin >> ret;
    return ret;
}

void get_ans(vector<pair<int, int>> candsA, vector<pair<int, int>> candsB) {
    vector<int> a, b;
    for (auto ra: candsA) {
        for (int i = ra.first; i <= ra.second; i++) a.push_back(i);
    }
    for (auto rb: candsB) {
        for (int i = rb.first; i <= rb.second; i++) b.push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        isOn[i] = false;
    }
    for (auto x: a) isOn[x] = true;
    int lo = 0, hi = a.size()-1;
    int idxA = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        for (int i = 0; i <= mid; i++) {
            isOn[a[i]] = false;
        }
        int tot = ask();
        for (int i = 0; i <= mid; i++) {
            isOn[a[i]] = true;
        }
        if (tot % 2 == 0) {
            idxA = mid;
            hi = mid-1;
        }
        else {
            lo = mid+1;
        }
    }
    int idxB = -1;
    lo = 0, hi = b.size() - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        for (int i = 0; i <= mid; i++) {
            isOn[b[i]] = true;
        }
        int tot = ask();
        for (int i = 0; i <= mid; i++) {
            isOn[b[i]] = false;
        }
        if (tot % 2 == 0) {
            idxB = mid;
            hi = mid-1;
        }
        else {
            lo = mid+1;
        }
    }
    cout << "! " << a[idxA] - 1 << " " << b[idxB] - 1 << endl;
}

void solve() {
    cin >> n;
    int fin = 1;
    vector<pair<int, int>> blocks = {{1, n}};
    while (true) {
        vector<pair<int, int>> nxt;
        for (auto [l, r]: blocks) {
            if (l == r) continue;
            int mid = (l + r) / 2;
            nxt.push_back({l, mid});
            nxt.push_back({mid+1, r});
        }
        blocks = nxt;
        int sz = blocks.size();
        for (int i = 1; i <= n; i++) {
            isOn[i] = false;
        }
        for (int i = 0; i < sz; i += 2) {
            for (int j = blocks[i].first; j <= blocks[i].second; j++) {
                isOn[j] = true;
            }
        }
        int tot = ask();
        if (tot % 2 == 0) continue;
        vector<pair<int, int>> candsA, candsB;
        for (int i = 0; i < sz; i++) {
            if (i % 2 == 0) {
                candsA.push_back(blocks[i]);
            }
            else candsB.push_back(blocks[i]);
        }
        get_ans(candsA, candsB);
        return;
    }
}

int main() {
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...