分数: 450 点
问题陈述
给你整数 N,M,一系列 N 整数 X=(X_1,X_2,\ldots,X_N),以及一系列 M 整数 Y=(Y_1,Y_2,\ldots,Y_M).
判断是否存在 N 行按 M 列整数矩阵 A=(A_{i,j}) (1\le i\le N,\ 1\le j\le M) 满足以下所有条件,如果满足,则找到一个这样的矩阵。
- 1\le A_{i,j} \le N\times M
- 全部 N\times M 的元素 A_{i,j} 是不同的。
- \displaystyle \max_{1\le j\le M} A_{i,j} = X_i 为 i=1,2,\ldots,N.
- \displaystyle \max_{1\le i\le N} A_{i,j} = Y_j 为 j=1,2,\ldots,M.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T\le 10^5
- 1\le N,M
- 总和 N\times M 所有测试用例最多 2\times 10^5.
- 1\le X_i,Y_j\le N\times M
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N M X_1 X_2 \ldots X_N Y_1 Y_2 \ldots Y_M
输出
按顺序输出测试用例的答案,以换行符分隔。
对于每个测试用例,如果没有 A 满足所有条件,输出 No.
否则,输出 A 满足以下格式的所有条件:
Yes
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
如果有多个 A 满足条件的,其中任何一个都将被接受。
示例输入 1
3 2 3 5 6 5 3 6 3 3 5 4 6 6 2 4 5 4 18 20 19 14 17 18 20 14 15
示例输出 1
Yes 5 1 4 2 3 6 No Yes 18 12 4 9 13 20 1 10 16 19 6 8 2 5 14 3 11 17 7 15
考虑第一个测试用例。
在示例输出中,所有元素 A 之间 1 和 6 和 是不同的,而且,
- \displaystyle \max_{1\le j\le 3} A_{1,j} =\max \lbrace 5,1,4\rbrace = 5 = X_1
- \displaystyle\max_{1\le j\le 3} A_{2,j} =\max \lbrace 2,3,6\rbrace = 6 = X_2
- \displaystyle\max_{1\le i\le 2} A_{i,1} =\max \lbrace 5,2\rbrace = 5 = Y_1
- \displaystyle\max_{1\le i\le 2} A_{i,2} =\max \lbrace 1,3\rbrace = 3 = Y_2
- \displaystyle\max_{1\le i\le 2} A_{i,3} =\max \lbrace 4,6\rbrace = 6 = Y_3
所以所有条件都满足。
还接受其他输出,例如以下输出。
Yes 5 3 1 4 2 6