题目描述

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 仅利用给定的信息对隐藏排列进行排序，同时尽可能减少所需的交换次数。

实现细节

你需要实现函数：

void sortPermutation(int N);

该函数在每个测试点中会被调用一次，参数 $N$ 表示 Yan 需要排序的排列中的元素个数。在该函数（以及你编写的其他函数）中，你可以调用函数 $\verb|performSwap|$ 来交换排列中的两个元素，并会相应得到结果排列中循环的总个数。你必须保证在你的函数执行结束后，隐藏排列已被整理为递增顺序，即对所有 $0 \le i < N$ 满足 $P_i = i$，因为 Yan 会在该函数返回后立刻喊出 "Sorted"。

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$

子任务

只有当你的程序正确通过某个子任务中的所有测试时，你才能获得该子任务对应的分数比例。你的最终结果将基于 $Q$——即所有那些测试中调用 $\texttt{performSwap}$ 的最多次数——来计算：

翻译由 DeepSeek V4 Pro 完成