← 返回题目列表

AtCoder · agc064_e

E. 叉和构造

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

分数: 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.