CF1383D Rearrange

考拉 Koa 有一个 $n$ 行 $m$ 列的矩阵 $A$。该矩阵的元素是 $1$ 到 $n \cdot m$ 的互不相同的整数（每个数恰好出现一次）。 对于任意 $n$ 行 $m$ 列的矩阵 $M$，我们定义如下内容： - $M$ 的第 $i$ 行定义为 $R_i(M) = [M_{i1}, M_{i2}, \ldots, M_{im}]$，对于所有 $i$（$1 \le i \le n$）。 - $M$ 的第 $j$ 列定义为 $C_j(M) = [M_{1j}, M_{2j}, \ldots, M_{nj}]$，对于所有 $j$（$1 \le j \le m$）。 Koa 定义 $S(A) = (X, Y)$ 为 $A$ 的谱，其中 $X$ 是 $A$ 每一行的最大值组成的集合，$Y$ 是 $A$ 每一列的最大值组成的集合。 更正式地说： - $X = \{ \max(R_1(A)), \max(R_2(A)), \ldots, \max(R_n(A)) \}$ - $Y = \{ \max(C_1(A)), \max(C_2(A)), \ldots, \max(C_m(A)) \}$ Koa 要求你构造一个 $n$ 行 $m$ 列的矩阵 $A'$，使得每个 $1$ 到 $n \cdot m$ 的整数恰好出现一次，并且满足以下条件： - $S(A') = S(A)$ - 对于所有 $i$（$1 \le i \le n$），$R_i(A')$ 是双调的 - 对于所有 $j$（$1 \le j \le m$），$C_j(A')$ 是双调的 一个数组 $t$（$t_1, t_2, \ldots, t_k$）被称为双调的，如果它先严格递增后严格递减。更正式地说：存在某个位置 $p$（$1 \le p \le k$），使得 $t_1 < t_2 < \ldots < t_p > t_{p+1} > \ldots > t_k$。 请你帮助 Koa 找到这样一个矩阵，或者判断不存在这样的矩阵。

输入的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 250$），表示矩阵 $A$ 的行数和列数。 接下来的 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示矩阵 $A$ 的元素 $A_{ij}$（$1 \le A_{ij} \le n \cdot m$）。保证 $1$ 到 $n \cdot m$ 的每个数在矩阵中恰好出现一次。

如果不存在这样的矩阵，输出一行 $-1$。 否则，输出 $n$ 行，每行 $m$ 个用空格分隔的整数，描述矩阵 $A'$。 第 $i$ 行第 $j$ 个数表示 $A'_{ij}$。 $A'$ 中每个 $1$ 到 $n \cdot m$ 的整数恰好出现一次，每行每列都必须是双调的，并且 $S(A) = S(A')$。 如果有多组解，输出任意一组均可。

我们来分析第一个样例： 对于矩阵 $A$： - 行： - $R_1(A) = [3, 5, 6]$，$\max(R_1(A)) = 6$ - $R_2(A) = [1, 7, 9]$，$\max(R_2(A)) = 9$ - $R_3(A) = [4, 8, 2]$，$\max(R_3(A)) = 8$ - 列： - $C_1(A) = [3, 1, 4]$，$\max(C_1(A)) = 4$ - $C_2(A) = [5, 7, 8]$，$\max(C_2(A)) = 8$ - $C_3(A) = [6, 9, 2]$，$\max(C_3(A)) = 9$ - $X = \{6, 9, 8\}$ - $Y = \{4, 8, 9\}$ - 所以 $S(A) = (X, Y) = (\{6, 9, 8\}, \{4, 8, 9\})$ 对于矩阵 $A'$： - 行： - $R_1(A') = [9, 5, 1]$，$\max(R_1(A')) = 9$ - $R_2(A') = [7, 8, 2]$，$\max(R_2(A')) = 8$ - $R_3(A') = [3, 6, 4]$，$\max(R_3(A')) = 6$ - 列： - $C_1(A') = [9, 7, 3]$，$\max(C_1(A')) = 9$ - $C_2(A') = [5, 8, 6]$，$\max(C_2(A')) = 8$ - $C_3(A') = [1, 2, 4]$，$\max(C_3(A')) = 4$ - 注意每个数组都是双调的。 - $X = \{9, 8, 6\}$ - $Y = \{9, 8, 4\}$ - 所以 $S(A') = (X, Y) = (\{9, 8, 6\}, \{9, 8, 4\})$。 由 ChatGPT 4.1 翻译