Submission #1360421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1360421		kawhiet	Dark Ride (EGOI25_darkride)	C++20	100 / 100	7 ms	6780 KiB

Main

#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;
    auto ask = [&](vector<int> pos) {
        string s(n, '0');
        for (auto i : pos) {
            s[i] = '1';
        }
        cout << "? " << s << endl;
        int ret;
        cin >> ret;
        return ret;
    };
    vector<vector<int>> s1(20, vector<int>(n));
    vector<vector<int>> s2(20, vector<int>(n));
    for (int i = 0; (1 << i) < n; i++) {
        int x = (1 << i);
        vector<int> pos;
        for (int j = 0; j < n; j += 2 * x) {
            for (int k = j; k < min(j + x, n); k++) {
                pos.push_back(k);
            }
        }
        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;
        if (ask(pos) % 2 == 1) {
            vector<int> ans;
            while (l + 1 < r) {
                int m = (l + r) / 2;
                vector<int> t = s;
                for (int j = 0; j <= m; j++) {
                    t.push_back(pos[j]);
                }
                if (ask(t) % 2 == 0) {
                    r = m;
                } else {
                    l = m;
                }
            }
            ans.push_back(pos[r]);
            set<int> rem;
            for (int j = 0; j < i; j++) {
                for (int k = 0; k < n; k++) {
                    if (s2[j][k] && s1[j][ans[0]]) {
                        rem.insert(k);
                    }
                    if (s1[j][k] && s2[j][ans[0]]) {
                        rem.insert(k);
                    }
                }
            }
            vector<int> s_nw;
            for (auto k : s) {
                if (!rem.count(k)) {
                    s_nw.push_back(k);
                } 
            }
            swap(s, s_nw);
            l = -1, r = s.size() - 1;
            while (l + 1 < r) {
                int m = (l + r) / 2;
                vector<int> t = pos;
                for (int j = 0; j <= m; j++) {
                    t.push_back(s[j]);
                }
                if (ask(t) % 2 == 0) {
                    r = m;
                } else {
                    l = m;
                }
            }
            ans.push_back(s[r]);
            cout << "! " << ans[0] << ' ' << ans[1] << '\n';
            return 0;
        }
        for (auto j : pos) s1[i][j] = true;
        for (auto j : s) s2[i][j] = true;
    }
    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 9 / 9
• Subtask 3: 15 / 15
• Subtask 4: 17 / 17
• Subtask 5: 16 / 16
• Subtask 6: 14 / 14
• Subtask 7: 29 / 29