제출 #1335698

#제출 시각아이디문제언어결과실행 시간메모리
1335698ezzzayDark Ride (EGOI25_darkride)C++20
100 / 100
1 ms560 KiB
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    if (!(cin >> N)) return 0;

    // number of bits we need
    int M = 0;
    while ((1 << M) < N) ++M;
    vector<int> r(M);

    // Step 1: M queries, query i: turn on switches with (s >> i) & 1 == 1
    for (int i = 0; i < M; ++i) {
        string q(N, '0');
        for (int s = 0; s < N; ++s) {
            if ((s >> i) & 1) q[s] = '1';
        }
        cout << "? " << q << endl;          // endl flushes
        int val;
        if (!(cin >> val)) return 0;
        r[i] = val & 1; // only parity matters
    }

    // Compute X = A xor B from the parities
    int X = 0;
    for (int i = 0; i < M; ++i) if (r[i]) X |= (1 << i);

    // find a bit position where X has 1
    int pos = -1;
    for (int i = 0; i < M; ++i) if ((X >> i) & 1) { pos = i; break; }
    if (pos == -1) {
        // should not happen in valid tests (A != B)
        // fallback: output 0 0
        cout << "! 0 0" << endl;
        return 0;
    }

    // group1: indices with bit pos == 1
    vector<int> g;
    for (int s = 0; s < N; ++s) if ((s >> pos) & 1) g.push_back(s);

    // binary search inside g to find the special switch in this group
    int lo = 0, hi = (int)g.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        string q(N, '0');
        for (int j = lo; j <= mid; ++j) q[g[j]] = '1';
        // ensure all other switches (including the whole other group) are off
        cout << "? " << q << endl;
        int val;
        if (!(cin >> val)) return 0;
        if (val % 2 == 1) {
            // the special switch within group g is in [lo..mid]
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }

    int found = g[lo];
    int other = found ^ X;

    cout << "! " << found << " " << other << endl;
    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...