← 返回题目列表

Codeforces · 1375/D

D. 替换为 MEX

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

给你一个 $$$n$$$ 整数数组,介于 $$$0$$$ 和 $$$n$$$ 之间(含)。

在一次操作中,您可以选择数组的任意元素并将其替换为数组元素的 MEX(操作后可能会发生变化)。

例如,如果当前数组为 $$$[0, 2, 2, 1, 4]$$$,则可以选择第二个元素并将其替换为当前元素的 MEX — $$$3$$$。数组将变为 $$$[0, 3, 2, 1, 4]$$$。

您必须使用最多 $$$2n$$$ 操作使数组非递减。

可以证明它总是可能的。请注意,您不必最小化操作次数。如果有很多解决方案,您可以打印其中任何一个。

–

数组 $$$b[1 \ldots n]$$$ 是非递减的当且仅当 $$$b_1 \le b_2 \le \ldots \le b_n$$$。

数组的 MEX(排除最小值)是不属于该数组的最小非负整数。例如:

- $$$[2, 2, 1]$$$ 的 MEX 是 $$$0$$$,因为 $$$0$$$ 不属于该数组。
- $$$[3, 1, 0, 1]$$$ 的 MEX 是 $$$2$$$,因为 $$$0$$$ 和 $$$1$$$ 属于数组,但 $$$2$$$ 不属于该数组。
- $$$[0, 3, 1, 2]$$$ 的 MEX 是 $$$4$$$,因为 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$ 属于该数组,但 $$$4$$$ 不属于该数组。

值得一提的是,长度为 $$$n$$$ 的数组的 MEX 始终在 $$$0$$$ 和 $$$n$$$ 之间(包含 $$$0$$$ 和 $$$n$$$)。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 1000$$$) — 数组的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$) — 数组的元素。请注意,它们不必是不同的。

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

输出

对于每个测试用例,您必须输出两行:

第一行必须包含一个整数 $$$k$$$ ($$$0 \le k \le 2n$$$) — 您执行的操作数。

第二行必须包含 $$$k$$$ 整数 $$$x_1, \ldots, x_k$$$ ($$$1 \le x_i \le n$$$),其中 $$$x_i$$$ 是为第 $$$i$$$ 操作选择的索引。

如果有很多解决方案,您可以找到其中任何一个。请记住,不需要最小化$$$k$$$。

示例

输入 #1

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

输出 #1

0

2
3 1
4
2 5 5 4
11
3 8 9 7 8 5 9 6 4 1 2
10
1 8 1 9 5 2 4 6 3 7

注意

在第一个测试用例中,数组已经是非递减的 ($$$2 \le 2 \le 3$$$)。

第二个测试用例的说明(每个操作修改的元素用红色表示):

- $$$a = [2, 1, 0]$$$ ;初始 MEX 为 $$$3$$$。
- $$$a = [2, 1, \color{红色}{3}]$$$ ;新的 MEX 为 $$$0$$$。
- $$$a = [\color{红色}{0}, 1, 3]$$$ ;新的 MEX 为 $$$2$$$。
- 最终数组是非递减的:$$$0 \le 1 \le 3$$$。

第三个测试用例说明:

- $$$a = [0, 7, 3, 1, 3, 7, 7]$$$ ;初始 MEX 为 $$$2$$$。
- $$$a = [0, \color{red}{2}, 3, 1, 3, 7, 7]$$$ ;新的 MEX 为 $$$4$$$。
- $$$a = [0, 2, 3, 1, \color{红色}{4}, 7, 7]$$$ ;新的 MEX 为 $$$5$$$。
- $$$a = [0, 2, 3, 1, \color{红色}{5}, 7, 7]$$$ ;新的 MEX 为 $$$4$$$。
- $$$a = [0, 2, 3, \color{红色}{4}, 5, 7, 7]$$$ ;新的 MEX 为 $$$1$$$。
- 最终数组是非递减的:$$$0 \le 2 \le 3 \le 4 \le 5 \le 7 \le 7$$$。