Codeforces Round 893 (Div. 2) |
---|
Закончено |
Леше подарили новую игру «НОД-перестановки». Каждый раунд этой игры проходит следующим образом:
Лёша уже сыграл несколько раундов и ему захотелось найти такую перестановку $$$a_1, a_2, \ldots, a_n$$$, что его счёт будет максимально возможным.
Напомним, что $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$, а $$$x \bmod y$$$ обозначает остаток от деления $$$x$$$ на $$$y$$$.
$$$^{\dagger}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).
Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Единственная строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \le n \le 10^5$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ различных целых чисел $$$a_{1},a_{2},\ldots,a_{n}$$$ ($$$1 \le a_i \le n$$$) — искомую перестановку.
Если существует несколько перестановок, на которых достигается максимальный счёт, вы можете вывести любую.
452710
1 2 4 3 5 1 2 1 2 3 6 4 5 7 1 2 3 4 8 5 10 6 9 7
В первом наборе входных данных Леше надо найти перестановку чисел от $$$1$$$ до $$$5$$$. Для перестановки $$$a=[1,2,4,3,5]$$$ массив $$$d$$$ равен $$$[1,2,1,1,1]$$$. Он содержит $$$2$$$ различных числа, что является максимумом среди всех перестановок из $$$5$$$ чисел. Существуют и другие ответы для этого набора входных данных.
Во втором наборе входных данных Леше надо найти перестановку чисел от $$$1$$$ до $$$2$$$. Всего существует две такие перестановки — $$$a=[1,2]$$$ и $$$a=[2,1]$$$. В обоих случаях массив $$$d$$$ равен $$$[1,1]$$$, поэтому обе перестановки являются корректным ответом.
В третьем наборе входных данных Леше надо найти перестановку чисел от $$$1$$$ до $$$7$$$. Для перестановки $$$a=[1,2,3,6,4,5,7]$$$ массив $$$d$$$ равен $$$[1,1,3,2,1,1,1]$$$. Он содержит $$$3$$$ различных числа, а значит и счёт раунда с такой перестановкой равен $$$3$$$. Можно показать, что не существует перестановки чисел от $$$1$$$ до $$$7$$$, счёт которой будет больше $$$3$$$.
Название |
---|