← 返回题目列表

AtCoder · arc111_c

C. 太重

中文机器翻译题面 查看原题

分数: 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

在初始状态下已经实现了目标。