Codeforces Global Round 9 |
---|
Закончено |
Вам дан массив из $$$n$$$ целых чисел от $$$0$$$ до $$$n$$$ включительно.
За одну операцию вы можете выбрать любой элемент массива и заменить его на MEX всех элементов массива (этот 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 массива равен наименьшему неотрицательному целому числу, которое не принадлежит массиву. Например:
Стоит отметить, что MEX массива длины $$$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$$$ не требуется.
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
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$$$).
Объяснение второго набора входных данных (элемент, изменяемый каждой операцией, окрашен красным):
Объяснение третьего набора входных данных:
Название |
---|