/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
あなたは、色 C_1, C_2, \ldots, C_N の N 個のボールを持っています。 ここで、すべての色は 1 以上 N 以下の整数により表されます。 あなたは、これらのボールを円周上に並べようとしています。その後、色のペア (X, Y) であって、X < Y であり、色 X と Y の二つの隣接するボールが存在するようなペアの個数を数えます。
そのようなペアの個数を最小化する配置を求めてください。そのような配置が多数存在する場合は、そのうちのいずれかを求めてください。
例えば、色 1, 1, 2, 3 のボールについて、1, 1, 2, 3 と並べると、(1, 2), (2, 3), (1, 3) という 3 つのペアが現れます。1, 2, 1, 3 と並べると、現れるペアは (1, 2), (1, 3) の 2 つのみです。
各入力ファイルについて、T 個のテストケースを解いてください。
制約
- 1 \le T \le 5 \cdot 10^4
- 3 \le N \le 2 \cdot 10^5
- 1 \le C_i \le N
- 各入力ファイル内の N の総和は 2\cdot 10^5 を超えない。
- 入力中のすべての値は整数である。
入力
入力は標準入力から以下の形式で与えられる。
T case_1 case_2 \vdots case_T
各ケースは以下の形式である。
N C_1 C_2 \ldots C_N
出力
各テストケースについて、答えを以下の形式で出力せよ。
A_1 A_2 \ldots A_N
ここで、A_i は配置における円周上の（時計回りに見て）i 番目のボールの色である。
(A_1, A_2, \ldots, A_N) は (C_1, C_2, \ldots, C_N) を並べ替えたものでなければならない。また、色のペア (X, Y) であって、X < Y であり、色 X と Y の二つの隣接するボールが存在するようなペアの個数が最小化されていなければならない。
複数の解が存在する場合は、そのいずれも認められる。
入力例 1
3 3 1 2 3 4 1 2 1 3 5 2 2 5 3 3
出力例 1
1 2 3 2 1 3 1 3 3 2 5 2
Score : 700 points
Problem Statement
You have N balls of colors C_1, C_2, \ldots, C_N. Here, all colors are represented by an integer between 1 and N inclusive. You want to arrange the balls on a circle. After you do that, you will count the number of pairs of colors (X, Y) such that X < Y and there exist two adjacent balls of colors X and Y.
Find an arrangement that minimizes the number of such pairs. If there are many such arrangements, find any of them.
For example, for balls of colors 1, 1, 2, 3, if we arrange them as 1, 1, 2, 3, we get 3 pairs: (1, 2), (2, 3), (1, 3). If we arrange them as 1, 2, 1, 3, we get only 2 pairs: (1, 2), (1, 3).
Solve T test cases for each input file.
Constraints
- 1 \le T \le 5 \cdot 10^4
- 3 \le N \le 2 \cdot 10^5
- 1 \le C_i \le N
- The sum of N in one input file doesn't exceed 2\cdot 10^5.
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is in the following format:
N C_1 C_2 \ldots C_N
Output
For each test case, output your answer in the following format:
A_1 A_2 \ldots A_N
Here, A_i is the color of the i-th ball (in clockwise order) on the circle in your arrangement.
(A_1, A_2, \ldots, A_N) should be a permutation of (C_1, C_2, \ldots, C_N), and the number of pairs of colors (X, Y) such that X < Y and there exist two adjacent balls of colors X and Y, should be minimized.
If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 3 1 2 3 4 1 2 1 3 5 2 2 5 3 3
Sample Output 1
1 2 3 2 1 3 1 3 3 2 5 2