B - Swap and Maximize
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : {100} 点
問題文
長さ N の数列 A =(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。
あなたは次の操作を 0 回以上好きな回数行うことができます。
- 整数 i\ (1 \le i \le N) を選ぶ。 A_i と B_i を入れ替える。
数列のスコアを \displaystyle\sum_{i=1}^N \sum_{j=1}^N \mathrm{min} (A_i,B_j) で定めます。
あなたの目標は操作後の数列のスコアを最大化することです。 スコアの最大値を達成するような操作後の数列を一つ出力してください。 そのような数列が複数存在する場合、どれを出力しても構いません。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 入力は全て整数
- 1 \le T \le 2 \times 10^5
- 1 \le N \le 2 \times 10^5
- 1 \le A_i , B_i \le 10^8
- ひとつの入力について、含まれるテストケースの N の総和は 2 \times 10^5 を超えない
入力
入力は以下の形式で標準入力から与えられる。
T \mathrm{case}_1 \vdots \mathrm{case}_T
各ケースは以下の形式で与えられる。
N A_1 \ldots A_N B_1 \ldots B_N
出力
操作後の数列 A',B' であって、スコアの最大値を達成するようなものを次の形式で出力せよ。
答えが複数存在する場合はどれを出力してもかまわない。
A'_1 \ldots A'_N B'_1 \ldots B'_N
入力例 1
2 3 1 2 3 4 5 6 2 1 2 2 1
出力例 1
4 2 6 1 5 3 1 2 2 1
1 つ目のケースでは、例えば i=1 とする操作と、 i=3 とする操作を行うことにより、スコアの最大値 22 を達成できます。
2 つ目のケースでは、例えば操作を行わないことにより、スコアの最大値 5 を達成できます。