← 返回题目列表

Codeforces · 2178/D

D. 圣诞节或歇斯底里

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

集体歇斯底里(炉石传说)
$$$\color{白色}{\text{你是sus}}$$$

富兰克林正在策划一场圣诞节袭击,他在其中施展了咒语 集体歇斯底里 在一个精灵村庄。

有$$$n$$$个精灵,编号为$$$1$$$到$$$n$$$,其中精灵$$$i$$$的生命值为$$$h_i$$$,攻击值为$$$a_i$$$。 最初,对于所有 $$$i$$$,$$$h_i=a_i$$$ 且所有 $$$a_i$$$ 都是不同的。 Elf $$$i$$$ 还活着当且仅当其健康状况为正(即 $$$h_i \gt 0$$$)。

当富兰克林施放时 集体歇斯底里,重复以下过程:

  • 选择一对不同的活着的精灵 $$$x$$$ 和 $$$y$$$ ($$$h_x,h_y \gt 0$$$) 使得精灵 $$$x$$$ 有 不 之前受到过攻击。如果不存在这样的对,则终止该过程。
  • 然后,精灵$$$x$$$攻击精灵$$$y$$$,使$$$h_y$$$减少$$$a_x$$$。此外,由于反冲,$$$h_x$$$ 减少了$$$a_y$$$。请注意,$$$a_x$$$ 和 $$$a_y$$$ 保持不变。

该过程将重复,直到无法选择一对有效的精灵为止。可以证明 集体歇斯底里 最多在 $$$n$$$ 次迭代后终止。

给定一个整数$$$m$$$,构造一个有效的攻击序列,使得当进程结束时$$$m$$$精灵还活着;或确定不存在这样的序列。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2\le n\le 2\cdot 10^5, 0\le m\le n$$$) — 村庄中的精灵数量和存活的精灵数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — 初始攻击 和 精灵的健康值。

保证所有 $$$a_i$$$ 都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10 ^ 5$$$。

输出

对于每个测试用例,如果 $$$m$$$ 精灵不可能存活,则打印 $$$-1$$$。

否则,输出有效的攻击序列,如下所示:

  • 在第一行,输出一个整数 $$$k$$$ ($$$0\le k\le n$$$) — 中的迭代次数 集体歇斯底里.
  • 接下来是 $$$k$$$ 行,第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1\leq x_i,y_i\leq n$$$, $$$x_i\neq y_i$$$),表明 elf $$$x_i$$$ 攻击 elf第 $$$i$$$ 次迭代中的 $$$y_i$$$。

该序列必须满足以下所有条件:

  • 在第 $$$i$$$ 次迭代之前,精灵 $$$x_i$$$ 和 $$$y_i$$$ 都活着,并且精灵 $$$x_i$$$ 在之前的任何迭代中都没有受到攻击。
  • 在第 $$$k$$$ 次迭代之后,恰好 $$$m$$$ 精灵还活着,并且不存在一对不同的活着精灵 $$$x$$$ 和 $$$y$$$ 使得精灵 $$$x$$$ 之前没有攻击过。

如果有多个答案,则可以输出其中任何一个。任何满足上述条件的有效序列都将被接受。

示例

输入
复制

7
4 2
1 4 2 3
2 2
6 7
3 0
1 2 3
3 1
1 2 3
3 2
1 2 3
4 1
2 3 4 5
6 0
998244353 1000000000 314159265 676767677 999999999 987654321

输出
复制

2
3 1
2 4
-1
2
3 2
1 3
2
1 2
3 2
-1
2
1 4
4 2
4
3 1
2 5
6 1
4 2

注意

在第一个测试用例中,一个可能的攻击序列如下所示:

#$$$x$$$$$$y$$$攻击后的生命值已攻击的精灵
0——$$$[1, 4, 2, 3]$$$$$$[]$$$
1$$$3$$$$$$1$$$$$$[-1, 4, 1, 3]$$$$$$[3]$$$
2$$$2$$$$$$4$$$$$$[-1, 1, 1, -1]$$$$$$[2, 3]$$$

经过 $$$2$$$ 迭代后,只有精灵 $$$2$$$ 和 $$$3$$$ 还活着。由于他们都已经攻击过,不可能再进行有效的攻击,并且 集体歇斯底里 终止。

在第二个测试用例中,第一次迭代中 $$$(x,y)$$$ 的唯一可能选择是 $$$(1,2)$$$ 或 $$$(2,1)$$$。无论哪种情况,精灵 $$$1$$$ 最终都会获得 $$$-1$$$ 生命值,因此两个精灵最终都不可能都活着。请注意 集体歇斯底里 将持续至少一次迭代,因为第一次迭代存在有效的 $$$(x,y)$$$。

在第六个测试用例中,在所有攻击后,只有 elf $$$3$$$ 还活着。尽管精灵$$$3$$$之前没有攻击过, 集体歇斯底里 终止,因为没有其他精灵可以攻击。