猜排列（hard）

算法思路

将隐藏排列看成有向边 $i\to p_{i}$。每个点的入度和出度均为 $1$，因此构成若干个置换环。 我们先利用交换反馈确定环的结构，再判断每个长环的方向。

1. 交换并复原，建立无向图。

枚举每对 $i<j$，连续执行两次 S i j。 第一次得到反馈 $r$，第二次恢复自然排列，得到基准反馈 $k$。 第一对位置的两次交换就能取得 $k$，无需额外询问；若 $k=n$，直接提交自然排列。

记 $[P]$ 表示条件 $P$ 成立时为 $1$，否则为 $0$。 由于只有位置 $i,j$ 发生变化，第一次交换带来的差值为

$$D_{i,j}=r-k=[p_{i}=j]+[p_{j}=i]-[p_{i}=i]-[p_{j}=j].$$

若某个端点是固定点，则 $D_{i,j}<0$；否则，差值就是这两个编号之间的有向边数。 因此，将所有 $D_{i,j}>0$ 的点对连成无向边后，连通分量只有三种：

• 孤立点：固定点，令 $p_{i}=i$。

• 两个点组成的一条边：二元环，令 $p_{i}=j,\ p_{j}=i$。

• 长度至少为 $3$ 的环：相邻关系已知，还需判断两个方向。

2. 连续交换，确定长环方向。

沿一个长环依次记下 $c_{1},c_{2},\ldots,c_{L}$。 该环尚未被修改，环内仍为自然顺序；记此时的当前总匹配数为 $b$。 依次交换

$$(c_{1},c_{2}),(c_{2},c_{3}),\ldots,(c_{L-1},c_{L}).$$

输出时将每对下标按从小到大排列。这 $L-1$ 次交换后，环内变成

$$a_{c_1}=c_{2},\quad a_{c_2}=c_{3},\quad\ldots,\quad a_{c_L}=c_{1}.$$

若最后一次反馈为 $b+L$，说明上述方向正确；若为 $b$，说明方向相反。 据此填写该环的答案。

不同环互不影响，已处理的环无需复原。 每次用最新反馈作为下一个环的基准，不能始终使用最初的 $k$。 全部确定后，用 ! 提交隐藏排列；当前摆放不必已经等于答案。 每次输出都需刷新缓冲区，读到 $-1$ 或输入结束时立即退出。

正确性证明

交换只改变两个位置，因此差值公式成立。 正差值恰好对应隐藏排列中相邻的两个编号，故构造出的无向图准确保留了置换环结构。 固定点和二元环可以直接还原，长环只剩方向不确定。

处理一个长环时，环内原本没有正确位置，环外状态保持不变。 所构造的方向若正确，环内全部 $L$ 个位置正确；若相反，由于 $L\ge3$，环内没有正确位置。 因此反馈分别为 $b+L$ 和 $b$，可以唯一确定方向。 逐个还原所有分量，即可得到完整的隐藏排列。

复杂度分析

设所有长环长度为 $L_{1},\ldots,L_{c}$。交换询问次数至多为

$$Q\le 2\binom n2+\sum_{t=1}^{c}(L_{t}-1) \le n(n-1)+(n-1)=n^{2}-1\le9999.$$

时间复杂度为 $O(n^{2})$。图中每个点的度数至多为 $2$，空间复杂度为 $O(n)$。

按单空格、LF 换行输出，每条交换询问最多 $9$ 字节，最终答案最多 $294$ 字节。 总输出的一个粗略上界为

$$9999\times9+294=90285<99999,$$

因此同时满足询问次数和输出字节限制。