← 返回题目列表

Codeforces · 1896/C

C. 匹配数组

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

给定两个数组 $$$a$$$ 和 $$$b$$$,大小为 $$$n$$$。数组 $$$a$$$ 和 $$$b$$$ 的美妙之处在于索引 $$$i$$$ 的数量,使得 $$$a_i > b_i$$$。

您还获得了一个整数 $$$x$$$。确定是否可以重新排列 $$$b$$$ 的元素,使数组的美丽变成 $$$x$$$。如果可能,输出 $$$b$$$ 的一个有效重新排列。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 2\cdot 10^5$$$, $$$0 \le x \le n$$$) - 数组 $$$a$$$ 和 $$$b$$$ 的大小以及所需的数组美观度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$) — 数组 $$$a$$$ 的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2n$$$) — 数组 $$$b$$$ 的元素。

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

输出

对于每个测试用例,如果无法重新排列 $$$b$$$ 以使数组的美观度等于 $$$x$$$,则输出“NO”。

否则,输出“YES”。然后,在下一行输出 $$$n$$$ 整数,表示 $$$b$$$ 的重新排列。

如果有多个解,则可以输出其中任何一个。

您可以在任何情况下(大写或小写)输出“YES”和“NO”。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

7
1 0
1
2
1 1
1
2
3 0
2 4 3
4 1 2
3 1
2 4 3
4 1 2
3 2
2 4 3
4 1 2
3 3
2 4 3
4 1 2
5 2
6 4 5 6 2
9 7 9 1 1

输出 #1

YES
2
NO
NO
YES
2 4 1
YES
4 1 2
NO
YES
1 9 9 7 1

注意

在测试用例 1 和 2 中,数组的美观度必须为 $$$0$$$,因为 $$$a_1 = 1 \le 2 = b_1$$$。

在测试用例 3、4、5 和 6 中,数组唯一可能的优点是 $$$x = 1$$$ 和 $$$x = 2$$$。特别是,如果$$$b$$$重新排列为$$$[2, 4, 1]$$$,则$$$a_3 = 3 > 1 = b_3$$$,因此数组的美丽在于$$$1$$$。如果 $$$b$$$ 保持与给定输入相同的顺序,则 $$$a_2 = 4 > b_2 = 1$$$ 和 $$$a_3 = 3 > 2 = b_3$$$,因此数组的美妙之处在于 $$$2$$$。