307616: CF1383D. Rearrange
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Rearrange
题意翻译
给出一个大小为 $N \times M$ 的矩阵 $a$，矩阵内的元素 $\in [1 , N \times M]$，且两两不同 **下面给出一些定义：** $R_i$ 为第 $i$ 行的元素集合，即$R_i=\{a_{i,1},a_{i,2},...,a_{i,m}\}$ $C_j$ 为第 $j$ 列的元素集合，即$C_j=\{a_{1,j},a_{2,j},...,a_{n,j}\}$ $X$ 为矩阵每一行的最大元素的集合，$Y$ 为矩阵每一列的最大元素的集合，即 $X = \{\max(R_1),\max(R_2),..,\max(R_n)\}$ $Y = \{\max(C_1),\max(C_2),..,\max(C_m)\}$ $S(a) = (X , Y)$ 求构造一个新的 $N \times M$ 的矩阵 $a'$ 使其满足 - 矩阵内的元素 $\in [1 , N \times M]$，且两两不同 - $S(a') = S(a)$ - 对于任意的行或列，使其满足先上升后下降，即存在 $k$ 满足 行：$a_{i,1}<a_{i,2}<...<a_{i,k}>a_{i,k+1}>...>a_{i,M}$ 列：$a_{1,j}<a_{2,j}<...<a_{k,j}>a_{k+1,j}>...>a_{N,j}$ 如果存在多种合法构造，输出其中一种；若不存在，请输出 $-1$题目描述
Koa the Koala has a matrix $ A $ of $ n $ rows and $ m $ columns. Elements of this matrix are distinct integers from $ 1 $ to $ n \cdot m $ (each number from $ 1 $ to $ n \cdot m $ appears exactly once in the matrix). For any matrix $ M $ of $ n $ rows and $ m $ columns let's define the following: - The $ i $ -th row of $ M $ is defined as $ R_i(M) = [ M_{i1}, M_{i2}, \ldots, M_{im} ] $ for all $ i $ ( $ 1 \le i \le n $ ). - The $ j $ -th column of $ M $ is defined as $ C_j(M) = [ M_{1j}, M_{2j}, \ldots, M_{nj} ] $ for all $ j $ ( $ 1 \le j \le m $ ). Koa defines $ S(A) = (X, Y) $ as the spectrum of $ A $ , where $ X $ is the set of the maximum values in rows of $ A $ and $ Y $ is the set of the maximum values in columns of $ A $ . More formally: - $ 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 asks you to find some matrix $ A' $ of $ n $ rows and $ m $ columns, such that each number from $ 1 $ to $ n \cdot m $ appears exactly once in the matrix, and the following conditions hold: - $ S(A') = S(A) $ - $ R_i(A') $ is bitonic for all $ i $ ( $ 1 \le i \le n $ ) - $ C_j(A') $ is bitonic for all $ j $ ( $ 1 \le j \le m $ ) An array $ t $ ( $ t_1, t_2, \ldots, t_k $ ) is called bitonic if it first increases and then decreases. More formally: $ t $ is bitonic if there exists some position $ p $ ( $ 1 \le p \le k $ ) such that: $ t_1 < t_2 < \ldots < t_p > t_{p+1} > \ldots > t_k $ . Help Koa to find such matrix or to determine that it doesn't exist.输入输出格式
输入格式
The first line of the input contains two integers $ n $ and $ m $ ( $ 1 \le n, m \le 250 $ ) — the number of rows and columns of $ A $ . Each of the ollowing $ n $ lines contains $ m $ integers. The $ j $ -th integer in the $ i $ -th line denotes element $ A_{ij} $ ( $ 1 \le A_{ij} \le n \cdot m $ ) of matrix $ A $ . It is guaranteed that every number from $ 1 $ to $ n \cdot m $ appears exactly once among elements of the matrix.
输出格式
If such matrix doesn't exist, print $ -1 $ on a single line. Otherwise, the output must consist of $ n $ lines, each one consisting of $ m $ space separated integers — a description of $ A' $ . The $ j $ -th number in the $ i $ -th line represents the element $ A'_{ij} $ . Every integer from $ 1 $ to $ n \cdot m $ should appear exactly once in $ A' $ , every row and column in $ A' $ must be bitonic and $ S(A) = S(A') $ must hold. If there are many answers print any.
输入输出样例
输入样例 #1
3 3
3 5 6
1 7 9
4 8 2输出样例 #1
9 5 1
7 8 2
3 6 4输入样例 #2
2 2
4 1
3 2输出样例 #2
4 1
3 2输入样例 #3
3 4
12 10 8 6
3 4 5 7
2 11 9 1输出样例 #3
12 8 6 1
10 11 9 2
3 4 5 7