[IOI 2015] Sorting 排序
题目描述
Aizhan 有一个由整数 0,1,…,N−1 组成的排列 S,她想把它变成升序。Ermek 也会交换这个排列中的元素,他的交换计划预先给定。
两人按轮次交替操作。在第 i 轮(从 0 编号),Ermek 首先交换下标 Xi,Yi 处的元素,然后 Aizhan 选择两个下标进行一次交换。所选下标可以相同,此时序列不变。
如果一整轮开始前序列已经升序,排序过程立即结束。若 Ermek 在某轮中的交换已经使序列升序,Aizhan 可以交换两个相同下标来保持不变。若初始序列已经升序,所需轮数为 0。
已知 Ermek 的前 M 轮计划,并保证可以在至多 M 轮内排序。求最少轮数 R,以及 Aizhan 在这 R 轮中的一种交换方案。
输入格式
第一行一个整数 N。第二行 N 个整数 S0,S1,…,SN−1,给出初始排列。
第三行一个整数 M。接下来 M 行依次给出 Ermek 每轮交换的两个下标 Xi,Yi。
输出格式
第一行输出最少轮数 R。
接下来恰好 R 行。第 i+2 行输出两个下标 Pi,Qi,表示 Aizhan 在第 i 轮交换的位置,其中 0≤i<R。下标从 0 开始,任意一种最短的合法方案均可。
样例
样例输入 #1
5
4 3 2 1 0
6
0 1
1 2
2 3
3 4
0 1
1 2
样例输出 #1
3
0 4
1 3
3 4
样例输入 #2
5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4
样例输出 #2
3
1 4
4 2
2 2
样例 1 的交换过程:
| 轮次 |
Ermek 交换后 |
Aizhan 交换后 |
| 0 |
(3,4,2,1,0) |
(0,4,2,1,3) |
| 1 |
(0,2,4,1,3) |
(0,1,4,2,3) |
| 2 |
(0,1,2,4,3) |
(0,1,2,3,4) |
样例 2 的交换过程:
| 轮次 |
Ermek 交换后 |
Aizhan 交换后 |
| 0 |
(3,0,4,2,1) |
(3,1,4,2,0) |
| 1 |
(0,1,4,2,3) |
(0,1,3,2,4) |
| 2 |
(0,1,2,3,4) |
数据范围
1≤N≤200000,1≤M≤600000。所有交换下标在 [0,N−1] 内。
原赛子任务如下。本地题面统一要求 R 最小。
| 子任务 |
分值 |
N 的范围 |
M |
Ermek 的交换 |
原赛对 R 的要求 |
| 1 |
8 |
1≤N≤5 |
N2 |
始终交换 (0,0) |
R≤M |
| 2 |
12 |
1≤N≤100 |
30N |
| 3 |
16 |
始终交换 (0,1) |
| 4 |
18 |
1≤N≤500 |
无附加限制 |
| 5 |
20 |
6≤N≤2000 |
3N |
最小 |
| 6 |
26 |
6≤N≤200000 |