Submission #1357754

#TimeUsernameProblemLanguageResultExecution timeMemory
1357754neptunnsDark Ride (EGOI25_darkride)C++20
100 / 100
39 ms2088 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long
#define maxn 500005
#define mi LLONG_MIN
#define ma LLONG_MAX
#define mod 1000000007
#define pb push_back
#define S second
#define F first
int ask(string s) {
    int ans;
    cout << "? " << s << endl;
    cin >> ans;
    return ans;
}
void answer(int a, int b) {
    cout << "! " << a << " " << b << endl;
    exit(0);
}
void solve() {
    int n, a = -1, b = -1;
    cin >> n;
    vector<pair<string, int>> vec;
    vector<pair<int, int>> hl;
    hl.pb({0, n - 1});
    string s(n, '0'), str(n, '0');

    while (true) {
        bool ok = 1;
        for (auto [l, r] : hl) {
            if (l < r) {
                ok = 0;
                break;
            }
        }
        if (ok) break;

        s = str;
        vector<pair<int, int>> nhl;
        for (auto [l, r] : hl) {
            if (l < r) {
                int m = (l + r) / 2;
                for (int i = l; i <= m; i++) s[i] = '1';
                nhl.pb({l, m});
                nhl.pb({m + 1, r});
            } else {
                nhl.pb({l, r});
            }
        }

        vec.pb({s, ask(s)});
        hl = nhl;
    }
    string ns;
    for (auto [ss, answ] : vec) {
        if (answ % 2) {
            ns = ss;
        }
    }
    vector<int> v;
    for (int i = 0; i < ns.size(); i++) {
        if (ns[i] == '1') {
            v.pb(i);
        }
    }
    int sz = v.size();
    int l = 0, r = sz - 1;
    while (l < r) {
        int m = (l + r) / 2;
        s = str;
        for (int i = l; i <= m; i++) s[v[i]] = '1';
        int res = ask(s);
        vec.pb({s, res});
        if (res % 2)
            r = m;
        else
            l = m + 1;
    }
    a = v[r];

    for (int x = 0; x < n; x++) {
        if (x == a) continue;
        bool ok = 1;
        for (auto [ss, y] : vec) {
            if ((ss[x] == ss[a]) != (y % 2 == 0)) {
                ok = 0;
                break;
            }
        }

        if (ok) {
            b = x;
            answer(a, b);
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
}
#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...