传送门：洛谷 CF2209C Find the Zero | Codeforces C. Find the Zero

更佳的阅读体验：CF2209C 题解

简要题意：IO 交互题。有一个长度 $2n$ 的隐藏数组，其中包含 $1 \sim n$ 各一个，以及 $n$ 个 $0$。每次询问可以查询两个位置的元素是否相等，你需要在不超过 $n + 1$ 次询问中找出一个值为 $0$ 的位置。

因为 $1 \sim n$ 的每个数都是出现且仅出现一次，所以如果某次询问得到了 $a_i = a_j$ 的结果，说明这两个都是 $0$，选一个输出即可。

如果 $a_i \ne a_j$，说明它们最多只有一个数是 $0$。如果我们直接排除掉这两个数，继续去考虑接下来的数，我们发现还剩下至少 $n - 1$ 个 $0$。那么我们每次都对两个未询问过的位置进行询问，经过 $n - 1$ 次询问后，如果仍然没有得到 $a_i = a_j$ 的反馈，我们就剩下了最后两个数。

如果这两个数也不相等呢？那就只剩下一次询问了，无法确定 $0$ 的位置。但如果将目光向前看呢？

我们随便找一对之前被我们询问过的位置，加上最后剩下的两个数，我们发现这四个数里至少包含两个 $0$。现在我们剩下两次询问，此时问题就简单许多了。

假设我们还没询问过的两个数是 $x, y$，从之前的询问中拿出来的两个数是 $a, b$。因为之前已经询问过 $a$ 和 $b$，所以此时就一定有 $a \ne b$。那如果我们抓住 $x$ 一个数，和 $a, b$ 分别比较，那就只有两种情况了。

如果 $x = a$ 或 $x = b$，那么显然 $x$ 一定是 $0$，直接输出即可。否则，未参与比较的 $y$ 就一定是 $0$。

#include <iostream>
using namespace std;

int t, n, stat;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        cin >> n;
        for (int i = 1; i < n; ++i) {
            cout << "? " << (i << 1) - 1 << ' ' << (i << 1) << '\n';
            cout.flush();
            cin >> stat;
            if (stat) {
                cout << "! " << (i << 1) << '\n';
                cout.flush();
                break;
            }
        } if (stat) continue;
        for (int i = 2; i <= 3; ++i) {
            cout << "? " << (n << 1) << ' ' << (n << 1) - i << '\n';
            cout.flush();
            cin >> stat;
            if (stat) {
                cout << "! " << (n << 1) << '\n';
                cout.flush();
                break;
            }
        } if (!stat) {
            cout << "! " << (n << 1) - 1 << '\n';
            cout.flush();
        }
    } return 0;
}