← 返回题目列表

AtCoder · arc208_d

D. 对称矩阵

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

分数: 700 点

问题陈述

给你一个整数序列 Y=(Y_1,Y_2,\ldots,Y_N) 长度 N 其中每个元素位于 1 和 N 包括在内。

判断是否存在 N \times N 整数矩阵 A=(A_{i,j}) (1\le i , j \le N) 满足以下所有条件,如果存在,找到一个这样的矩阵。

  • 1\le A_{i,j} \le N (1\le i \le N, 1\le j\le N)
  • A_{i,j}=A_{j,i} (1\le i\le N, 1\le j\le N)
  • A_{i,j_1}\neq A_{i,j_2} (1\le i\le N, 1\le j_1 < j_2 \le N)
  • A_{i,Y_i}=1 (1\le i\le N)

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1\le T\le 5000
  • 1\le N \le 500
  • 总和 N^2 所有测试用例最多 500^2.
  • 1\le Y_i\le N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N
Y_1 Y_2 \ldots Y_N

输出

按顺序输出每个测试用例的答案,以换行符分隔。

对于每个测试用例,如果不存在 A 满足所有条件,打印 No.

否则,打印 A 满足以下格式的所有条件:

Yes
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

如果有多个 A 满足所有条件,其中任何一个都将被接受。


示例输入 1

4
3
1 3 2
3
1 2 3
1
1
5
1 3 2 5 4

示例输出 1

Yes
1 2 3
2 3 1
3 1 2
No
Yes
1
Yes
1 2 5 4 3
2 3 1 5 4
5 1 4 3 2
4 5 3 2 1
3 4 2 1 5

考虑第一个测试用例。

可以验证的是 A 满足所有条件。除此之外,例如下面的 A 也将被接受:

1 3 2
3 2 1
2 1 3