题意

交互题。有 $N$ ($1\le N\le 4.3\cdot10^4$) 种矿石混在了一起，每种恰好有两块。有一个机器，初始为空，你可以加入/移除一块矿石，并询问机器里的矿石种类数量。求出哪 $N$ 对矿石种类相同，总操作数不超过 $10^6$。

题解

假设已知矿石能分为 $X$, $Y$ 两个集合，每个集合内有每种种类的矿石各一个，我们可以采取如下的分治策略：

• 选择 $X$ 集合中的一半矿石 $L$ 加入机器，然后依次加入 $Y$ 集合的每个矿石，如果种类数量没有改变，则与它配对的在 $L$ 中，否则在 $X\setminus L$ 中。将矿石全部移除，递归求解。

总询问次数 $3N\log N$，得分 $25$。

如果矿石被打乱了顺序，只需要依次加入所有矿石，如果种类数没有改变，说明与它配对的矿石在前面，否则在后面。这样就能把矿石分成上文所述的两个集合。加上清除矿石的代价，总询问次数 $4N+3N\log N$，得分 $40$。

接下来，可以发现有一些移除矿石的步骤是不必要的：

• $Y$ 集合的每一个矿石是否在机器中并不重要，我们只关心加入/移除矿石时种类数是否改变。
• 对于 $X$ 集合中的矿石，不论是 $L$ 在机器中，或是 $X\setminus L$ 在机器中，我们都能够确定与 $Y$ 集合的每一个矿石配对的矿石的位置。

至此，总询问次数减少到了 $2N+1.5N\log N$，得分 $80$。

最后是一些小优化：

• 如果确定与 $L$ 集合中的矿石配对的矿石数量已经等于 $|L|$，则剩余的 $Y$ 集合中的矿石都与 $X\setminus L$ 中的矿石配对；对于 $X\setminus L$ 同理；这样，我们得以在每次递归中节约至少 $1$ 次询问。
• 假设每次划分 $X$ 集合的比例为 $p$ 和 $1-p$，则总询问次数的递归式为 $T(N)=T(pN)+T((1-p)N)+(1+p)N$，经计算可得 $p=\frac{3-\sqrt5}2$ 时最优。

最终，总询问次数约为 $1.44N\log N$。

代码

#include "minerals.h"
#include <vector>
#include <numeric>
bool query(int x) {
    static int last = 0;
    int v = Query(x);
    if (v == last) {
        return false;
    } else {
        last = v;
        return true;
    }
}
void work(std::vector<int> x, std::vector<int> y, bool in) {
    if (int(x.size()) == 1) {
        Answer(x[0], y[0]);
    } else {
        int m = std::max(1, int(0.382 * x.size()));
        std::vector<int> yl, yr;
        for (int i = 0; i < m; ++i)
            query(x[i]);
        for (auto i : y) {
            if (int(yl.size()) == m) {
                yr.push_back(i);
            } else if (int(yr.size()) == int(x.size()) - m) {
                yl.push_back(i);
            } else if (query(i) != in) {
                yr.push_back(i);
            } else {
                yl.push_back(i);
            }
        }
        work(std::vector<int>(x.begin(), x.begin() + m), yl, !in);
        work(std::vector<int>(x.begin() + m, x.end()), yr, in);
    }
}
void Solve(int n) {
    std::vector<int> x, y;
    std::vector<bool> vis(2 * n);
    for (int i = 0; i < 2 * n; ++i)
        if (query(i + 1))
            vis[i] = true;
    for (int i = 0; i < 2 * n; ++i) {
        if (vis[i]) {
            x.push_back(i + 1);
        } else {
            y.push_back(i + 1);
        }
    }
    work(x, y, true);
}