UOJ Logo Universal Online Judge

UOJ

#233. 【IOI2015】Sorting

统计

Aizhan 有⼀个由 $N$ 个互不相同的整数组成的序列 $S[0], S[1], \ldots, S[N - 1]$,其中 $S[i]$ 取值范围是$[0, N - 1]$。Aizhan 试图通过交换某些元素对的⽅法将这个序列按照升序排序。Aizhan 的朋友 Ermek 也想交换某些元素对,Ermek 的交换未必有助于 Aizhan 的排序。

Ermek 和 Aizhan 打算通过若⼲轮次来修改这个序列。在每⼀轮,Ermek ⾸先做⼀次交换,然后 Aizhan 做另⼀次交换。更确切地说,做交换的⼈选择两个有效的下标并交换这两个下标的元素。请注意这两个下标可能相同。如果它们相等,则对这个元素⾃⾝做交换,并不改变这个序列。

Aizhan 知道 Ermek 并不关⼼对序列 $S$ 排序的事情。Aizhan 还知道 Ermek 将会选择哪些下标。Ermek 打算参加 $M$ 轮交换,将这些轮次从 $0$ 到 $M - 1$ 编号。对于 $0$ 到 $M - 1$ 之间的每个 $i$,Ermek 在第 $i$ 轮将选择下标 $X[i]$ 和 $Y[i]$ 的元素进⾏交换。

Aizhan 要对序列 $S$ 按升序进⾏排序。在每⼀轮之前,如果 Aizhan 看到当前的序列已经按升序排列,她将结束这个排序过程。给定初始序列 $S$ 以及 Ermek 要选择的下标,请你找出⼀个交换的序列,使得 Aizhan 能完成对序列 $S$ 的排序。此外,在有些⼦任务中,你还要找出尽可能短的交换序列来完成排序任务。题⽬保证通过 $M$ 或更少的轮次能够将序列 $S$ 排好序。

请注意如果 Aizhan 发现在 Ermek 的交换之后,序列 $S$ 已经排好序,则Aizhan可以选择交换两个相同下标(例如 $0$ 和 $0$)的元素。这样,序列 $S$ 在这⼀轮次之后也完成排序,于是也达到了 Aizhan 的⽬标。另外,如果初始序列 $S$ 就已经排好序,那么所需的最少排序轮数就是 $0$。

样例一

设:

  • 初始序列为 $S = 4, 3, 2, 1, 0$。
  • Ermek 打算做 $M = 6$ 轮交换。
  • Ermek打算选择的下标序列 $X$ 和 $Y$ 分别是 $X = 0, 1, 2, 3, 0, 1$ 和 $Y = 1, 2, 3, 4, 1, 2$。换句话说,Ermek 打算交换的下标对是 $(0, 1), (1, 2), (2, 3), (3, 4), (0, 1)$ 和 $(1, 2)$。

按照上述设定,Aizhan 能够通过三轮排序,将序列 $S$ 排序为 $0, 1, 2, 3, 4$。这三轮排序所选择的下标分别是 $(0, 4), (1, 3)$ 和 $(3, 4)$。

下表给出了 Ermek 和 Aizhan 修改这个序列的过程。

轮次 操作者 交换的下标对 序列
初态$4, 3, 2, 1, 0$
0Ermek$(0, 1)$$3, 4, 2, 1, 0$
0Aizhan$(0, 4)$$0, 4, 2, 1, 3$
1Ermek$(1, 2)$$0, 2, 4, 1, 3$
1Aizhan$(1, 3)$$0, 1, 4, 2, 3$
2Ermek$(2, 3)$$0, 1, 2, 4, 3$
2Aizhan$(3, 4)$$0, 1, 2, 3, 4$

样例二

设:

  • 初始序列为 $S = 3, 0, 4, 2, 1$。
  • Ermek 打算做 $M = 5$ 轮交换。
  • Ermek 打算交换的下标对是 $(1, 1), (4, 0), (2, 3), (1, 4)$ 和 $(0, 4)$。

按照上述设定,Aizhan 能够通过三轮完成对序列 $S$ 的排序。例如可通过选择下标对 $(1, 4), (4, 2)$ 和 $(2, 2)$ 来实现。下表给出了 Ermek 和 Aizhan 修改这个序列的过程。

轮次 操作者 交换的下标对 序列
初态$3, 0, 4, 2, 1$
0Ermek$(1, 1)$$3, 0, 4, 2, 1$
0Aizhan$(1, 4)$$3, 1, 4, 2, 1$
1Ermek$(4, 0)$$0, 1, 4, 2, 3$
1Aizhan$(4, 2)$$0, 1, 3, 2, 4$
2Ermek$(2, 3)$$0, 1, 2, 3, 4$
2Aizhan$(2, 2)$$0, 1, 2, 3, 4$

任务

给定序列 $S$、$M$ 和下标序列 $X$ 和 $Y$,请找出 Aizhan 对序列 $S$ 完成排序所需的交换的序列。在⼦任务 5-6 中,你找出的交换序列必须是最短的。

你需要实现函数 findSwapPairs:

  • findSwapPairs(N, S, M, X, Y, P, Q) — grader调⽤这个函数刚好⼀次。
    • N: 序列 $S$ 的⻓度.
    • S: ⼀个整数数组,表⽰初始序列 $S$。
    • M: Ermek 打算做交换的次数。
    • X, Y: ⻓度为 $M$ 的整数数组. 对于 $0\le i \le M - 1$, 在第 $i$ 轮 Ermek 打算交换下标为 $X[i]$ 和 $Y[i]$ 的数组。
    • P, Q: 整数数组。利⽤这两个数组报告 Aizhan 完成对序列 $S$ 排序的⼀种可能的交换序列,假设这个交换序列的⻓度为 $R$,对于 $0$ 到 $R$ 之间的每个 $R$,Aizhan在轮次 $i$ 选择的下标将被存⼊ $P[i]$ 和 $Q[i]$。 你可以假设数组 $P$ 和 $Q$ 均已分别被分配了 $M$ 个元素。
      • 这个函数应返回 $R$ 的值(定义如上)。

子任务

子任务 得分 $N$ $M$ $X, Y$ 的额外限制 对 $R$ 的要求
18$1 \leq N \leq 5$$M = N^2$$X[i] = Y[i] = 0$$R \le M$
212$1 \le N \le 100$$M = 30N$$X[i] = Y[i] = 0$$R \le M$
316$1 \leq N \leq 100$$M = 30N$$X[i] = 0, Y[i] = 1$$R \le M$
418$1 \leq N \leq 500$$M = 30N$$R \le M$
520$1 \leq N \leq 2000$$M = 3N$最小
626$1 \leq N \leq 200000$$M = 3N$最小

数据保证存在⼀个仅需 $M$ 或更少轮次的交换序列来完成排序。

实现细节

你只能提交一个源文件实现如上所述的 findSwapPairs 函数,并且遵循下面的命名和接口。你需要包含头文件 sorting.h。

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]);

评测方式

评测系统将读入如下格式的输入数据:

  • 第 $1$ 行:$N$
  • 第 $2$ 行:$S[0] \ldots S[N-1]$
  • 第 $3$ 行:$M$
  • 第 $4,\ldots, M + 3$ 行:$X[i]\ Y[i]$

评测系统将按下列格式输出:

  • 第 $1$ 行:findSwapPairs 函数的返回值 $R$
  • 第 $2 + i(0 \le i < R)$ 行:$P[i]\ Q[i]$

交互式类型的题目怎么本地测试

时间限制:$1\texttt{s}$

空间限制:$1500\texttt{MB}$

下载

样例及测评库下载