P16385 [IATI 2025] Cycles
题目描述
Yan 是一个勇敢的男孩，他总是选择从学校到祖母家的最短路径。不幸的是，这条路正好穿过一片闹鬼的森林。
一天，当 Yan 穿过森林时，他遇到了可怕的生物 Tung Tung Sahur。这个生物向他提出了一场比赛：如果 Yan 赢了，他就可以继续赶路——甚至还可能得到一份奖励。然而，如果他输了，Tung Tung Sahur 就会吃掉他。
游戏开始时，Tung Tung Sahur 会选择一个隐藏的、拥有 $N$ 个元素的排列 $P$。接下来轮到 Yan 进行操作。他可以反复选择排列中两个不同的位置，并要求 Tung Tung Sahur 交换这两个位置上的元素。Tung Tung Sahur 会执行交换，然后公布更新后的排列中**循环**的数量。这些交换是持久的——Tung Tung Sahur 不会撤销它们（但如果需要，Yan 完全可以重复一次交换以将其还原）。
任一由整数 $\{0, 1, \ldots, N - 1\}$ 构成的排列都可以分解为若干个不相交循环的集合。要找到这样一个循环，可以从任意下标 $i$ 开始，沿着映射 $i \mapsto P_i \mapsto P_{P_i} \mapsto \dots$ 一直走下去，直至回到 $i$——这些元素就形成了一个循环。例如，排列 $[1, 2, 0, 5, 4, 3]$ 表示映射 $0 \mapsto 1$、$1 \mapsto 2$、$2 \mapsto 0$、$3 \mapsto 5$、$4 \mapsto 4$ 以及 $5 \mapsto 3$，从而产生不相交循环 $(0\ 1\ 2)$、$(3\ 5)$ 和 $(4)$，所以它拥有 3 个循环。
在任何时刻，Yan 都可以通过喊出 $\texttt{Sorted}$ 来声明排列已经有序。如果此时排列确实按递增顺序排列，Tung Tung Sahur 就会放他离开。而且，Tung Tung Sahur 还会奖励 Yan 一些金币，奖励的多少取决于他用了多少次交换。因此，Yan 必须设法用尽可能少的交换次数将排列排序。
你的任务是帮助 Yan 仅利用给定的信息对隐藏排列进行排序，同时尽可能减少所需的交换次数。
### 实现细节
你需要实现函数：
```cpp
void sortPermutation(int N);
```
该函数在每个测试点中会被调用一次，参数 $N$ 表示 Yan 需要排序的排列中的元素个数。在该函数（以及你编写的其他函数）中，你可以调用函数 $\verb|performSwap|$ 来交换排列中的两个元素，并会相应得到结果排列中循环的总个数。你必须保证在你的函数执行结束后，隐藏排列已被整理为递增顺序，即对所有 $0 \le i < N$ 满足 $P_i = i$，因为 Yan 会在该函数返回后立刻喊出 "Sorted"。
```cpp
int performSwap(int x, int y);
```
调用 $\verb|performSwap|$ 表示交换元素 $P_x$ 与 $P_y$。注意，如果你用相同元素调用此函数，即 $x = y$，你将收到一个 Wrong Answer 判决。该函数接收以 $0$ 为基的下标 $x$ 和 $y$，并返回**更新后**排列中的循环数。
你的代码将与一个评测器（grader）一起编译，因此不应实现 $\verb|main|$ 函数，也不应从 $\verb|stdin|$ 读取或向 $\verb|stdout|$ 写入任何内容。你还需要包含头文件 $\verb|cycles.h|$。排列在调用 $\verb|sortPermutation|$ 之前已经固定，因此评测器并非自适应的。
### 本地测试
我们提供了一个本地评测器以及相应的头文件，以便你在本地测试程序。本地评测器首先读入 $N$，然后读入 $N$ 个从 $0$ 到 $N-1$ 的两两不同的数字。随后，它会调用你的 $\verb|sortPermutation|$ 函数，并期望该函数能正确地将排列排序。
输入格式
无
输出格式
无
说明/提示
### 样例测试
输入
```
3
2 0 1
```
交互过程
```
sortPermutation(3)
performSwap(0, 1): 返回 2
performSwap(0, 1): 返回 1
performSwap(0, 1): 返回 2
performSwap(1, 2): 返回 3
sortPermutation(3): 返回
```
### 约束条件
- $N = 1000$
### 子任务
| **子任务** | **分数** | **约束** | **附加约束** |
| :---: | :---: | :---: | :---: |
| 1 | $10$ | $N = 1000$ | 对于偶数 $i$：$(P_i, P_{i+1}) = (i, i+1)$ 或 $(i+1, i)$。 |
| 2 | $20$ | $N = 1000$ | 初始排列可以通过恰好一次交换完成排序。|
| 3 | $70$ | $N = 1000$ | -- |
只有当你的程序正确通过某个子任务中的所有测试时，你才能获得该子任务对应的分数比例。你的最终结果将基于 $Q$——即所有那些测试中调用 $\texttt{performSwap}$ 的最多次数——来计算：
| $Q$ 范围 | 得分比例 |
| :---: | :---: |
| $10^7 < Q$ | $0\%$ |
| $10^6 < Q \leq 10^7$ | $10\%$ |
| $9 \cdot 10^4 < Q \leq 10^6$ | $20\%$ |
| $3 \cdot 10^4 < Q \leq 9 \cdot 10^4$ | $60\%$ |
| $Q \leq 3 \cdot 10^4$ | $100\%$ |
翻译由 DeepSeek V4 Pro 完成