猜测总是有解。

有一个贪心的想法，每次选出 $a_i,b_j>0$、$a_i+b_j$ 最大且没选过的 $(i,j)$，填入一个没填过的数，然后令 $a_i,b_j-1$。剩下的每个空位至少一个行列是 0。然后再考虑怎么处理剩下的部分。

发现对于那些行列颜色数有一个不为 0 的格子是好做的，但是如果一个格子是 $(0,0)$，此时填的数应该在行列里都已经出现。但是可能不存在这样的数。

注意上面 bug 的原因是，当一个点变成 $(0,0)$ 的时候，不存在一个数同时在它所在的行列出现。所以我们认为构造：一开始先把每个 $(i,i)$ 填上 $n^2$，这样无论哪个格子都可以填 $n^2$ 而不改变行列的颜色数了。然后再按上面的方法做即可。