/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 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) からなる多重集合とします。
各要素が -10^{18} 以上 10^{18} 以下の整数である N \times N の行列 M に対し、スコアを以下のように定めます。
- S を N^2 個の値「M の i 行目または j 列目に属する 2N-1 要素の総和」 (1 \leq i,j \leq N)からなる多重集合とする。この時、スコアはすべての整数 z に対する \min( X に含まれる z の個数, S に含まれる z の個数) の総和。
スコアが最大となる行列 M を 1 つ求めてください。
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
- 1 つの入力に含まれるテストケースについて、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} はスコアが最大となる行列 M の i 行 j 列目の要素であり、-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
1 番目のケースの入出力では X=\{-5\}, S=\{-5\} であり、スコアは 1 です。
2 番目のケースの入出力では X=\{8,-11,7,-12\}, S=\{7,8,-11,-10\} であり、スコアは 3 です。
3 番目のケースの入出力では X=\{21,22,23,24,25,26,27,28,29\}, S=\{28,21,26,23,25,27,24,29,22\} であり、スコアは 9 です。
Score : 1300 points
Problem Statement
You are given a positive integer N and integer sequences of length N: A=(a_1,\ldots,a_N) and B=(b_1,\ldots,b_N).
Let X be the multiset of N^2 instances (a_i+b_j)(1 \leq i,j \leq N).
For an N \times N matrix M whose elements are integers between -10^{18} and 10^{18}, inclusive, we define the score as follows.
- Let S be the multiset of N^2 instances, each of which is the sum of the 2N-1 elements in the i-th row or j-th column of M (1 \leq i,j \leq N). Then, the score is the sum of \min(the multiplicity of z in X, the multiplicity of z in S) over all integers z.
Find a matrix M with the maximum score.
Solve the above problem for T cases.
Constraints
- 1 \leq T \leq 2.5 \times 10^5
- 1 \leq N \leq 500
- -10^9 \leq a_i,b_i \leq 10^9
- The sum of N^2 over the test cases in a single input is at most 2.5 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format, where \mathrm{test}_i represents the i-th test case:
T
\mathrm{test}_1
\vdots
\mathrm{test}_T
Each test case is given in the following format:
N a_1 \ldots a_N b_1 \ldots b_N
Output
For each test case, print a solution in the following format:
m_{1,1} \ldots m_{1,N}
\vdots
m_{N,1} \ldots m_{N,N}
Here, m_{i,j} is the element at the i-th row and j-th column of a matrix M with the maximum score, and must be an integer such that -10^{18} \leq m_{i,j} \leq 10^{18}.
If multiple matrices M have the maximum score, any one of them is accepted.
Sample Input 1
3 1 5 -10 2 0 -1 8 -11 3 20 23 26 1 2 3
Sample Output 1
-5 8 9 -10 -9 2 9 4 7 5 3 6 1 8
For the input and output in the first case, X=\{-5\}, S=\{-5\}, for a score of 1.
For the input and output in the second case, X=\{8,-11,7,-12\}, S=\{7,8,-11,-10\}, for a score of 3.
For the input and output in the third case, X=\{21,22,23,24,25,26,27,28,29\}, S=\{28,21,26,23,25,27,24,29,22\}, for a score of 9.