Submission #1363299

#TimeUsernameProblemLanguageResultExecution timeMemory
1363299biserailievaDark Ride (EGOI25_darkride)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

int n;

int ask(const vector<int>& ones) {
    string s(n, '0');
    for (int x : ones) s[x] = '1';
    cout << "? " << s << endl;
    int l; cin >> l;
    return l;
}

int find_one(vector<int> block) {
    int l = 0, r = (int)block.size() - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        vector<int> ones;
        for (int i = l; i <= mid; i++) ones.push_back(block[i]);
        int x = ask(ones);
        if (x % 2 == 1) r = mid;
        else l = mid + 1;
    }
    return block[l];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    vector<vector<int>> history_sets;
    vector<int> history_parity;

    vector<int> cur(n);
    iota(cur.begin(), cur.end(), 0);

    while (cur.size() > 1) {
        int mid = cur.size() / 2;
        vector<int> left(cur.begin(), cur.begin() + mid);

        int x = ask(left);

        history_sets.push_back(left);
        history_parity.push_back(x % 2);

        if (x % 2 == 1) {
            cur = left;
        } else {
            vector<int> right(cur.begin() + mid, cur.end());
            cur = right;
        }
    }

    int A = cur[0];

    vector<bool> possible(n, true);
    possible[A] = false;

    for (int i = 0; i < (int)history_sets.size(); i++) {
        auto &S = history_sets[i];
        vector<bool> inS(n, false);
        for (int x : S) inS[x] = true;

        for (int j = 0; j < n; j++) {
            if (j == A) continue;

            if (history_parity[i] == 1) {
                if (inS[A] == inS[j]) possible[j] = false;
            } else {
                if (inS[A] != inS[j]) possible[j] = false;
            }
        }
    }

    int B = -1;
    for (int i = 0; i < n; i++) {
        if (possible[i]) {
            B = i;
            break;
        }
    }

    cout << "! " << A << " " << B << 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...