← 返回题目列表

AtCoder · abc433_e

H. 最大矩阵 2

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

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