CF1868A.Fill in the Matrix
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
There is an empty matrix M of size n×m .
Zhongkao examination is over, and Daniel would like to do some puzzle games. He is going to fill in the matrix M using permutations of length m . That is, each row of M must be a permutation of length m† .
Define the value of the i -th column in M as vi=MEX(M1,i,M2,i,…,Mn,i)‡ . Since Daniel likes diversity, the beauty of M is s=MEX(v1,v2,⋯,vm) .
You have to help Daniel fill in the matrix M and maximize its beauty.
† A permutation of length m is an array consisting of m distinct integers from 0 to m−1 in arbitrary order. For example, [1,2,0,4,3] is a permutation, but [0,1,1] is not a permutation ( 1 appears twice in the array), and [0,1,3] is also not a permutation ( m−1=2 but there is 3 in the array).
‡ The MEX of an array is the smallest non-negative integer that does not belong to the array. For example, MEX(2,2,1)=0 because 0 does not belong to the array, and MEX(0,3,1,2)=4 because 0 , 1 , 2 and 3 appear in the array, but 4 does not.
输入格式
The first line of input contains a single integer t ( 1≤t≤1000 ) — the number of test cases. The description of test cases follows.
The only line of each test case contains two integers n and m ( 1≤n,m≤2⋅105 ) — the size of the matrix.
It is guaranteed that the sum of n⋅m over all test cases does not exceed 2⋅105 .
输出格式
For each test case, in the first line output a single integer — the maximum beauty of M .
Then output the matrix M of size n×m — the matrix you find.
If there are multiple solutions, you may output any of them.
输入输出样例
输入#1
4 4 3 1 16 6 6 2 1
输出#1
3 1 0 2 0 2 1 1 0 2 0 2 1 2 14 7 15 4 10 0 8 6 1 2 3 5 9 11 12 13 6 3 0 1 4 2 5 5 2 1 0 4 3 1 3 2 4 5 0 4 1 3 2 5 0 4 2 5 3 0 1 2 4 0 5 1 3 0 0 0
说明/提示
In the first test case:
- v1=MEX(1,0,1,0)=2 ;
- v2=MEX(0,2,0,2)=1 ;
- v3=MEX(2,1,2,1)=0 .
Therefore, s=MEX(2,1,0)=3 .
It can be shown that 3 is the maximum possible beauty of M .
In the second test case, any permutation will make s=2 .
In the third test case:
- v1=MEX(3,5,1,4,4,2)=0 ;
- v2=MEX(0,2,3,1,2,4)=5 ;
- v3=MEX(1,1,2,3,5,0)=4 ;
- v4=MEX(4,0,4,2,3,5)=1 ;
- v5=MEX(2,4,5,5,0,1)=3 ;
- v6=MEX(5,3,0,0,1,3)=2 .
Therefore, s=MEX(0,5,4,1,3,2)=6 .