分数: 600 点
问题陈述
有 N 人数 1 to N 和 N 件数为编号的行李 1 to N。 人 i 的重量为 a_i和行李 j 的重量为 b_j。 最初,人 i 有行李 p_i。我们希望执行零次或多次以下的操作,以便每个人 i 会有行李 i.
- 选择 i,j (i \neq j),并交换 Person 的行李 i 和人 j.
但是,当一个人携带一件重量为 大于或等于 他/她自己的体重,这个人会变得疲倦并且无法参加未来的操作(也就是说,我们不能选择他/她作为人) i or j)。 特别是,如果 a_i \leq b_{p_i}, 人 i 无法参与任何操作。
确定是否存在实现目标的操作序列,如果存在,则构造一个这样的序列 尽可能少的操作次数.
约束
- 1 \leq N \leq 200000
- 1 \leq a_i,b_i \leq 10^9
- p 是一个排列 1, \ldots, N.
- 输入的所有数字均为整数。
输入
输入由标准输入按以下格式给出:
N a_1 a_2 \ldots a_N b_1 b_2 \ldots b_N p_1 p_2 \ldots p_N
输出
如果没有操作序列达到目标,则打印 -1。
否则,按以下格式打印一系列操作:
K i_1 j_1 i_2 j_2 : i_K j_K
在这里, K 是操作次数,并且 i_t, j_t 代表在 t第次操作。
如果有多个解决方案,则接受其中任何一个。
示例输入 1
4 3 4 8 6 5 3 1 3 3 4 2 1
示例输出 1
3 3 4 1 3 4 2
最初,人们 1, 2, 3, 4 有件有重量的行李 1, 3, 3, 5分别,这样没人累。
首先我们进行选择Person的操作 3 和 4。现在,人们 1, 2, 3, 4 有件有重量的行李 1, 3, 5, 3,所以还没有人累。
其次,我们进行选择Person的操作 1 和 3。现在,人们 1, 2, 3, 4 有件有重量的行李 5, 3, 1, 3,所以人 1 累了。
最后我们进行选择Person的操作 4 和 2。现在,人们 1, 2, 3, 4 有件有重量的行李 5, 3, 1, 3,所以没有人会累。
这个操作顺序使每个人都拥有了正确的行李,并且操作次数尽可能少,因此是有效的。
示例输入 2
4 1 2 3 4 4 3 2 1 4 3 2 1
示例输出 2
-1
没有任何操作序列能够实现目标。
示例输入 3
1 58 998244353 1
示例输出 3
0
在初始状态下已经实现了目标。