题解

这是一道交互题，要求通过若干次查询找出一个隐藏的排列 $p$（满足 $p_i \neq i$）。查询方式为：给出一个排列 $q$，评测机返回满足 $i < j$、$p_{q_i} = q_j$ 且 $i \neq k$ 的二元组 $(i, j)$ 的数量。其中 $k$ 是程序一开始选择的固定常数。

---

核心思路

我们希望对每个位置 $i$，找出谁映射到它，即找到 $j$ 使得 $p_j = i$。

选择 $k$：取 $x = \lfloor \frac{n+1}{4} \rfloor$，令 $k = x + 1$。

数组划分：根据 $k$，将下标区间划分为三段：

$$A = [1,\; x], \quad B = [x+2,\; n-x], \quad C = [n-x+1,\; n] $$

注意位置 $k$ 本身是单独的特殊位置，不属于任何一段。

---

一次二分查询

假设我们要找 $p_j = i$ 的那个 $j$。

构造查询排列 $q$：

• 令 $q_k = i$（将 $i$ 放在特殊位置 $k$）。
• 将候选 $j$ 集合的一半填入 $A$ 和 $C$ 区域。
• 将候选集的另一半填入 $B$ 区域。

做两次查询：

1. 用构造好的 $q$ 查询一次，得到答案 $a$。
2. 将 $q$ 中除位置 $k$ 外的所有元素反转，再查询一次，得到答案 $b$。

---

为何 $a+b$ 能区分 $j$ 在哪一半？

考虑排列 $p$ 的边 $(u \to p_u)$ 组成的图（每个点出度为 $1$，入度为 $1$，形成若干环）。

对于目标 $i$，设 $p_j = i$，$p_i = t$。

• 边 $(j \to i)$（入边）：若 $j$ 在 $A \cup C$ 中，则它只会在某一次查询中被计数（因为反转会改变其位置是否在 $A \cup C$）。若 $j$ 在 $B$ 中，则两次查询都不会计数（因为 $B$ 中的下标与 $k$ 的距离使得不满足计数条件）。
• 边 $(i \to t)$（出边）：由于 $i$ 固定在位置 $k$，这条边永远不会被计数。
• 其他所有边：每次查询都会贡献恰好 $1$。

因此：

• 若 $j \in A \cup C$：$a+b = n-2$（所有边 $n-1$ 条，减去出边 $1$ 条，入边只计一次）。
• 若 $j \in B$：$a+b = n-1$（所有边，减去出边 $1$ 条，入边完全不计）。

通过比较 $a+b$ 的值，就能确定 $j$ 在哪一半！

---

二分查找 $j$

重复上述过程：

1. 将当前候选集分成两半。
2. 一半放入 $A \cup C$，另一半放入 $B$。
3. 用两次查询（正排 + 反转）判断 $j$ 落在哪一半。
4. 缩小候选集，继续递归。

每次迭代候选集大小减半，找到一个 $j$ 需要约 $2 \log n$ 次查询。找出全部 $n$ 个映射关系需要约 $2n \log n$ 次查询。当 $n \le 100$ 时，$2n \log_2 n < 15n$，满足查询次数限制。

---

算法步骤

1. 选择 $k = \lfloor \frac{n+1}{4} \rfloor + 1$。
2. 对每个未知的 $i$（$1$ 到 $n$）：
   • 初始化候选集为所有下标（除 $i$ 本身）。
   • 当候选集大小 $> 1$：
     • 将候选集均分，一半放入 $A \cup C$，另一半放入 $B$。
     • 令 $q_k = i$，构造 $q$。
     • 查询 $q$ 得 $a$，反转 $q$（除 $k$）查询得 $b$。
     • 若 $a+b = n-2$，则 $j$ 在前一半；否则在后一半。
     • 更新候选集。
   • 确定唯一的 $j$，记录 $p_j = i$。
3. 输出完整排列。

查询次数：$O(n \log n)$，在 $n \le 100$ 时远小于 $15n$。

---

代码参考

#include <bits/stdc++.h>
using namespace std;

int n, k;

int query(vector<int> &q) {
    cout << "? ";
    for (int i = 1; i <= n; i++) cout << q[i] << " \n"[i == n];
    cout.flush();
    int res;
    cin >> res;
    return res;
}

void solve() {
    cin >> n;
    k = (n + 1) / 4 + 1;
    cout << k << "\n";
    cout.flush();

    vector<int> p(n + 1, 0);
    for (int target = 1; target <= n; target++) {
        vector<int> cand;
        for (int j = 1; j <= n; j++) {
            if (j != target) cand.push_back(j);
        }

        while (cand.size() > 1) {
            int sz = cand.size();
            int half = sz / 2;
            vector<int> q(n + 1);
            int idx = 0;
            // 前半放入 A∪C，后半放入 B
            int ptra = 1, ptrc = n;
            for (int t = 0; t < half; t++) {
                int val = cand[idx++];
                if (ptra <= k - 1) q[ptra++] = val;
                else q[ptrc--] = val;
            }
            for (int t = half; t < sz; t++) {
                int val = cand[idx++];
                q[k + 1 + t - half] = val; // 填充 B 区
            }
            q[k] = target;

            int a = query(q);
            // 反转 q（除 k）
            reverse(q.begin() + 1, q.begin() + k);
            reverse(q.begin() + k + 1, q.end());
            int b = query(q);

            vector<int> new_cand;
            if (a + b == n - 2) {
                for (int t = 0; t < half; t++) new_cand.push_back(cand[t]);
            } else {
                for (int t = half; t < sz; t++) new_cand.push_back(cand[t]);
            }
            cand = new_cand;
        }
        p[cand[0]] = target;
    }

    cout << "! ";
    for (int i = 1; i <= n; i++) cout << p[i] << " \n"[i == n];
    cout.flush();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

注：上述实现为展示核心二分查找逻辑的简化版，实际下标填充需根据 $A,B,C$ 三段的大小精确控制。完整实现可见官方题解。