Codeforces Round 708 (Div. 2) |
---|
Закончено |
Дано число $$$n$$$ и массив $$$a_1, a_2, \ldots, a_n$$$. Необходимо переставить числа в массиве $$$a$$$ так, чтобы сумма $$$\textbf{MEX}$$$ на всех префиксах массива ($$$i$$$-й префикс — это $$$a_1, a_2, \ldots, a_i$$$) была максимальна.
Формально, вам нужно найти массив $$$b_1, b_2, \ldots, b_n$$$, такой что наборы чисел массивов $$$a$$$ и $$$b$$$ совпадают (то есть массив $$$b$$$ получается некоторой перестановкой чисел в массиве $$$a$$$) и $$$\sum\limits_{i=1}^{n} \textbf{MEX}(b_1, b_2, \ldots, b_i)$$$ максимальна.
Напомним, что $$$\textbf{MEX}$$$ множества целых неотрицательных чисел — такое минимальное целое неотрицательное число, которое не входит в это множество.
Например, $$$\textbf{MEX}(\{1, 2, 3\}) = 0$$$, $$$\textbf{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.
В первой строке находится единственное целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество наборов входных данных.
В первой строке описания каждого набора входных данных находится единственное целое число $$$n$$$ $$$(1 \le n \le 100)$$$.
Во второй строке описания каждого набора входных данных находится $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \le a_i \le 100)$$$.
Для каждого набора входных данных выведите массив $$$b_1, b_2, \ldots, b_n$$$, являющийся оптимальной перестановкой чисел $$$a_1, a_2, \ldots, a_n$$$, то есть сумма $$$\textbf{MEX}$$$ на всех его префиксах максимальна.
Если существует несколько оптимальных ответов, вы можете найти любой.
3 7 4 2 0 1 3 3 7 5 2 2 8 6 9 1 0
0 1 2 3 4 7 3 2 6 8 9 2 0
В первом наборе входных данных в ответе $$$\textbf{MEX}$$$ на префиксах будет таким:
Название |
---|