← 返回题目列表

AtCoder · utpc2021_b

B. 交换和最大化

中文机器翻译题面 查看原题

配点 : {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 可以实现。