Submission #1360298

#TimeUsernameProblemLanguageResultExecution timeMemory
1360298kawhietMonster-Go (EGOI25_monstergo)C++20
0 / 100
0 ms344 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    #ifdef LOCAL
    vector<int> p(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
    }
    #endif
    auto ask = [&](vector<int> pos) {
        string s(n, '0');
        for (auto i : pos) {
            s[i] = '1';
        }
        #ifdef LOCAL
        string t(n, ' ');
        for (int i = 0; i < n; i++) {
            t[p[i]] = s[i];
        }
        int c = 0;
        for (int i = 1; i < n; i++) {
            c += t[i] != t[i - 1];
        }
        return c;
        #endif
        cout << "? " << s << endl;
        int ret;
        cin >> ret;
        return ret;
    };
    for (int i = 0; (1 << i) < n; i++) {
        int x = 1 << i;
        vector<int> pos;
        for (int j = 0; j < min(j + x, n); j += x) {
            for (int k = j; k < min(j + x, n); k++) {
                pos.push_back(k);
            }
            j += x;
        }
        if (ask(pos) % 2 == 1) {
            cout << "! ";
            vector<bool> vis(n);
            for (auto j : pos) {
                vis[j] = true;
            }
            vector<int> s;
            for (int j = 0; j < n; j++) {
                if (!vis[j]) {
                    s.push_back(j);
                }
            }
            int l = -1, r = pos.size() - 1;
            while (l + 1 < r) {
                int m = (l + r) / 2;
                vector<int> t = s;
                for (int i = 0; i <= m; i++) {
                    t.push_back(pos[i]);
                }
                if (ask(t) % 2 == 0) {
                    r = m;
                } else {
                    l = m;
                }
            }
            cout << pos[r] << ' ';
            l = -1, r = s.size() - 1;
            while (l + 1 < r) {
                int m = (l + r) / 2;
                vector<int> t = pos;
                for (int i = 0; i <= m; i++) {
                    t.push_back(s[i]);
                }
                if (ask(t) % 2 == 0) {
                    r = m;
                } else {
                    l = m;
                }
            }
            cout << s[r] << '\n';
            return 0;
        }
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...