308452: CF1521E. Nastia and a Beautiful Matrix
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Nastia and a Beautiful Matrix
题意翻译
你有 $k$ 个数字,他们分别是 $1,2,3,...,k$,对于数字 $i$ 你有相同的 $a_i$ 个。 定义一个 $n\times n$ 的矩阵为美丽矩阵: - 这个 $n\times n$ 的矩阵包含了你所拥有的所有数字; - 对于每个 $2\times 2$ 的子矩阵,占用的格子不能超过 $3$(当一个格子的数为 $0$ 时,我们认为它没有被占用)并且每个对角线的数字是不同的; 现在,你要构造一个最小的美丽矩阵。题目描述
You like numbers, don't you? Nastia has a lot of numbers and she wants to share them with you! Isn't it amazing? Let $ a_i $ be how many numbers $ i $ ( $ 1 \le i \le k $ ) you have. An $ n \times n $ matrix is called beautiful if it contains all the numbers you have, and for each $ 2 \times 2 $ submatrix of the original matrix is satisfied: 1. The number of occupied cells doesn't exceed $ 3 $ ; 2. The numbers on each diagonal are distinct. Make a beautiful matrix of minimum size.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10\,000 $ ) — the number of test cases. The first line of each test case contains $ 2 $ integers $ m $ and $ k $ ( $ 1 \le m, k \le 10^5 $ ) — how many numbers Nastia gave you and the length of the array $ a $ , respectively. The second line of each test case contains $ k $ integers $ a_1, a_2, \ldots, a_{k} $ ( $ 0 \le a_i \le m $ , $ a_1 + a_2 + \ldots + a_{k} = m $ ), where $ a_i $ is how many numbers $ i $ you have. It's guaranteed that the sum of $ m $ and $ k $ in one test doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each $ t $ test case print a single integer $ n $ — the size of the beautiful matrix. In the next $ n $ lines print $ n $ integers $ b_{i, j} $ ( $ 0 \le b_{i, j} \le k $ ; if position is empty, print $ b_{i, j} = 0 $ ) — the beautiful matrix $ b $ you made up.
输入输出样例
输入样例 #1
2
3 4
2 0 0 1
15 4
2 4 8 1
输出样例 #1
2
4 1
0 1
5
3 0 0 2 2
3 2 3 3 0
0 1 0 4 0
3 0 0 0 0
2 1 3 3 3