← 返回题目列表

Codeforces · 1738/D

D. 排列成瘾者

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

给定从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$a_1, a_2, \dots, a_n$$$ 以及阈值 $$$k$$$ 和 $$$0 \leq k \leq n$$$,您可以按如下方式计算序列 $$$b_1, b_2, \dots, b_n$$$。

对于每个按升序排列的 $$$1 \leq i \leq n$$$,令 $$$x = a_i$$$。

- 如果 $$$x \leq k$$$,则将 $$$b_{x}$$$ 设置为 $$$a_j$$$ ($$$1 \leq j < i$$$) 且 $$$a_j > k$$$ 的最后一个元素。如果不存在这样的元素$$$a_j$$$,则设置$$$b_{x} = n+1$$$。
- 如果 $$$x > k$$$,则将 $$$b_{x}$$$ 设置为 $$$a_j \leq k$$$ 的最后一个元素 $$$a_j$$$ ($$$1 \leq j < i$$$)。如果不存在这样的元素$$$a_j$$$,则设置$$$b_{x} = 0$$$。

不幸的是,在序列 $$$b_1, b_2, \dots, b_n$$$ 被完全计算之后,排列 $$$a_1, a_2, \dots, a_n$$$ 和阈值 $$$k$$$ 被丢弃。

现在你只有序列 $$$b_1, b_2, \dots, b_n$$$。你的任务是找到任何可能的排列 $$$a_1, a_2, \dots, a_n$$$ 和阈值 $$$k$$$ 产生序列 $$$b_1, b_2, \dots, b_n$$$。保证至少存在一对排列 $$$a_1, a_2, \dots, a_n$$$ 和阈值 $$$k$$$ 产生序列 $$$b_1, b_2, \dots, b_n$$$。

从 $$$1$$$ 到 $$$n$$$ 的整数排列是一个长度为 $$$n$$$ 的序列,其中包含从 $$$1$$$ 到 $$$n$$$ 的所有整数恰好一次。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。以下行包含每个测试用例的描述。

每个测试用例的第一行包含一个整数$$$n$$$ ($$$1 \leq n \leq 10^5$$$),表示排列$$$a$$$的长度。

每个测试用例的第二行包含$$$n$$$整数$$$b_1, b_2, \dots, b_n$$$ ($$$0 \leq b_i \leq n+1$$$),表示序列$$$b$$$的元素。

保证至少存在一对排列 $$$a_1, a_2, \dots, a_n$$$ 和阈值 $$$k$$$ 产生序列 $$$b_1, b_2, \dots, b_n$$$。

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

输出

对于每个测试用例,在第一行输出阈值 $$$k$$$ ($$$0 \leq k \leq n$$$),然后在第二行输出排列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) 使得排列 $$$a_1, a_2, \dots, a_n$$$ 和阈值 $$$k$$$ 产生序列 $$$b_1, b_2, \dots, b_n$$$。如果有多个解,可以输出任意一个。

示例

输入 #1

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

输出 #1

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

注意

对于第一个测试用例,排列 $$$a = [1,3,2,4]$$$ 和阈值 $$$k = 2$$$ 将产生如下序列 $$$b$$$。

- 当 $$$i = 1$$$、$$$x = a_i = 1 \leq k$$$ 时,不存在 $$$a_j$$$ ($$$1 \leq j < i$$$) $$$a_j > k$$$。因此,$$$b_1 = n + 1 = 5$$$。
- 当 $$$i = 2$$$、$$$x = a_i = 3 > k$$$ 时,$$$a_j \leq k$$$ 的最后一个元素 $$$a_j$$$ 为 $$$a_1$$$。因此,$$$b_3 = a_1 = 1$$$。
- 当 $$$i = 3$$$、$$$x = a_i = 2 \leq k$$$ 时,$$$a_j > k$$$ 的最后一个元素 $$$a_j$$$ 为 $$$a_2$$$。因此,$$$b_2 = a_2 = 3$$$。
- 当 $$$i = 4$$$、$$$x = a_i = 4 > k$$$ 时,$$$a_j \leq k$$$ 的最后一个元素 $$$a_j$$$ 为 $$$a_3$$$。因此,$$$b_4 = a_3 = 2$$$。

对于第二个测试用例,排列 $$$a = [1,2,3,4,5,6]$$$ 和阈值 $$$k = 3$$$ 将生成序列 $$$b$$$,如下所示。

- 当 $$$i = 1, 2, 3$$$, $$$a_i \leq k$$$ 时,不存在 $$$a_j$$$ ($$$1 \leq j < i$$$) $$$a_j > k$$$。因此,$$$b_1 = b_2 = b_3 = n + 1 = 7$$$。
- 当 $$$i = 4, 5, 6$$$, $$$a_i > k$$$ 时,$$$a_j \leq k$$$ 的最后一个元素 $$$a_j$$$ 是 $$$a_3$$$。因此,$$$b_4 = b_5 = b_6 = a_3 = 3$$$。

对于第三个测试用例,排列 $$$a = [6,5,4,3,2,1]$$$ 和阈值 $$$k = 3$$$ 将生成序列 $$$b$$$,如下所示。

- 当 $$$i = 1, 2, 3$$$, $$$a_i > k$$$ 时,不存在 $$$a_j$$$ ($$$1 \leq j < i$$$) $$$a_j \leq k$$$。因此,$$$b_4 = b_5 = b_6 = 0$$$。
- 当 $$$i = 4, 5, 6$$$, $$$a_i \leq k$$$ 时,$$$a_j > k$$$ 的最后一个元素 $$$a_j$$$ 为 $$$a_3$$$。因此,$$$b_1 = b_2 = b_3 = a_3 = 4$$$。