分数: 1300 点
问题陈述
给你一个正整数 N 和长度的整数序列 N: A=(a_1,\ldots,a_N) 和 B=(b_1,\ldots,b_N).
让 X 是以下的多重集 N^2 实例 (a_i+b_j)(1 \leq i,j \leq N).
对于 N \times N 矩阵 M 其元素是介于 -10^{18} 和 10^{18},包含在内,我们将分数定义如下。
- 让 S 是以下的多重集 N^2 实例,每个实例都是 2N-1 中的元素 i第行或 j第 列 M (1 \leq i,j \leq N)。那么,得分就是 \min(的多重性 z in X,多重性 z in S) 所有整数 z.
求一个矩阵 M 得分最高。
解决上述问题 T 案例。
约束
- 1 \leq T \leq 2.5 \times 10^5
- 1 \leq N \leq 500
- -10^9 \leq a_i,b_i \leq 10^9
- 总和 N^2 单个输入中的测试用例最多 2.5 \times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \mathrm{test}_i 代表 i-第一个测试用例:
T
\mathrm{test}_1
\vdots
\mathrm{test}_T
每个测试用例均按以下格式给出:
N a_1 \ldots a_N b_1 \ldots b_N
输出
对于每个测试用例,按以下格式打印解决方案:
m_{1,1} \ldots m_{1,N}
\vdots
m_{N,1} \ldots m_{N,N}
在这里, m_{i,j} 是位于 i第行和 j矩阵的第列 M 具有最高分数,并且必须是一个整数,使得 -10^{18} \leq m_{i,j} \leq 10^{18}.
如果多个矩阵 M 具有最高分数,其中任何一项均被接受。
样本输入 1
3 1 5 -10 2 0 -1 8 -11 3 20 23 26 1 2 3
示例输出 1
-5 8 9 -10 -9 2 9 4 7 5 3 6 1 8
对于第一种情况的输入和输出, X=\{-5\}, S=\{-5\},得分为 1.
对于第二种情况的输入和输出, X=\{8,-11,7,-12\}, S=\{7,8,-11,-10\},得分为 3.
对于第三种情况的输入和输出, X=\{21,22,23,24,25,26,27,28,29\}, S=\{28,21,26,23,25,27,24,29,22\},得分为 9.