Code: Binary Strings are Simple?

#include <bits/stdc++.h>

#define int long long

void solve() {
    int n;
    std::cin >> n;
    if (n == -1) {
        return;
    }

    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);

    auto check = [&](int st) -> bool {
        std::vector<int> a;
        for (int i = st; i <= n; i += 2) {
            a.push_back(i);
        }

        int sz = a.size();
        std::vector<double> dist(sz + 1, 1e9);
        std::vector<int> q(sz + 1, -1);
        std::vector<bool> vis(sz + 1, false);

        dist[0] = 0;

        for (int i = 0; i < sz; ++i) {
            int u = -1;
            for (int j = 0; j < sz; ++j) {
                if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }
            vis[u] = true;

            if (q[u] != -1) {
                int tu = a[u], tv = a[q[u]];
                std::cout << "? " << std::min(tu, tv) + 1 << " "
                          << std::max(tu, tv) << std::endl;

                int ok;
                std::cin >> ok;
                if (ok == -1) {
                    return false;
                }

                int w = ((std::abs(tu - tv)) / ok) % 2;
                adj[tu].push_back({tv, w});
                adj[tv].push_back({tu, w});
            }

            for (int v = 0; v < sz; ++v) {
                if (!vis[v]) {
                    double tc = 1.0 / std::abs(a[u] - a[v]);
                    if (tc < dist[v]) {
                        dist[v] = tc;
                        q[v] = u;
                    }
                }
            }
        }
        return true;
    };

    if (!check(0)) {
        return;
    }
    if (!check(1)) {
        return;
    }

    std::vector<int> pre(n + 1);
    auto dfs = [&](auto self, int u, int p) -> void {
        for (auto [v, w] : adj[u]) {
            if (v != p) {
                pre[v] = pre[u] ^ w;
                self(self, v, u);
            }
        }
    };

    dfs(dfs, 0, -1);
    dfs(dfs, 1, -1);

    std::string s = "";
    for (int i = 1; i <= n; ++i) {
        s += std::to_string(pre[i - 1] ^ pre[i]);
    }

    std::cout << "! " << s << std::endl;
    int ok;
    std::cin >> ok;
    if (ok == 1 || ok == -1) {
        return;
    }

    for (auto &c : s) {
        c = (c == '0' ? '1' : '0');
    }
    std::cout << "! " << s << std::endl;
    std::cin >> ok;
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

    int _ = 1;
    std::cin >> _;

    while (_--) {
        solve();
    }

    return 0;
}