← 返回题目列表

Codeforces · 1768/C

C. 元素减压

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

找到长度为 $$$n$$$ 的两个排列 $$$^\dagger$$$ $$$p$$$ 和 $$$q$$$,使得 $$$\max(p_i,q_i)=a_i$$$ 对于所有 $$$1 \leq i \leq n$$$ 或报告这样的 $$$p$$$ 和 $$$q$$$ 不存在。

$$$^\dagger$$$ 长度 $$$n$$$ 的排列是一个数组,由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成,且顺序任意。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

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

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

输出

对于每个测试用例,如果不存在满足条件的$$$p$$$和$$$q$$$,则输出“NO”(不带引号)。

否则,输出“YES”(不带引号),然后输出 $$$2$$$ 行。第一行应包含 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$,第二行应包含 $$$n$$$ 整数 $$$q_1,q_2,\ldots,q_n$$$。

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

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

示例

输入 #1

3
1
1
5
5 3 4 2 5
2
1 1

输出 #1

YES
1 
1 
YES
1 3 4 2 5 
5 2 3 1 4 
NO

注意

在第一个测试用例中,$$$p=q=[1]$$$。这是正确的,因为 $$$a_1 = max(p_1,q_1) = 1$$$。

在第二个测试用例中,$$$p=[1,3,4,2,5]$$$ 和 $$$q=[5,2,3,1,4]$$$。这是正确的,因为:

- $$$a_1 = \max(p_1, q_1) = \max(1, 5) = 5$$$,
- $$$a_2 = \max(p_2, q_2) = \max(3, 2) = 3$$$,
- $$$a_3 = \max(p_3, q_3) = \max(4, 3) = 4$$$,
- $$$a_4 = \max(p_4, q_4) = \max(2, 1) = 2$$$,
- $$$a_5 = \max(p_5, q_5) = \max(5, 4) = 5$$$。

在第三个测试用例中,可以表明不存在这样的 $$$p$$$ 和 $$$q$$$ 。