/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
非負整数を要素とする H 行 W 列の行列 A が与えられます。 1 \leq i \leq H かつ 1 \leq j \leq W を満たす整数の組 (i, j) について、 A の i 行目 j 列目の要素を A_{i, j} で表します。
A に対して以下の手順を行います。
- まず、A の要素のうち 0 であるものそれぞれを、任意の正の整数で置き換える（ 0 である要素が複数ある場合、それぞれを異なる正の整数で置き換えることもできます）。
-
その後、「下記の 2 つの操作のどちらかを行うこと」を好きな回数（ 0 回でも良い）だけ行う。
- 1 \leq i \lt j \leq H を満たす整数の組 (i, j) を選び、A の i 行目と j 行目を入れ替える。
- 1 \leq i \lt j \leq W を満たす整数の組 (i, j) を選び、A の i 列目と j 列目を入れ替える。
A が次の条件を満たすようにすることができるかどうかを判定してください。
-
A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}
-
言い換えると、1 \leq i, i' \leq H および 1 \leq j, j' \leq W を満たす任意の 2 つの整数の組 (i, j) と (i', j') について、下記の 2 つの条件がともに成り立つ。
- i \lt i' ならば A_{i, j} \leq A_{i', j'}
- 「 i = i' かつ j \lt j' 」ならば A_{i, j} \leq A_{i', j'}
制約
- 2 \leq H, W
- H \times W \leq 10^6
- 0 \leq A_{i, j} \leq H \times W
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}
出力
A が問題文中の条件を満たすようにできる場合は Yes を、できない場合は No を出力せよ。
入力例 1
3 3 9 6 0 0 4 0 3 0 3
出力例 1
Yes
以下の手順で操作を行うことで、A が問題文中の条件を満たすようにすることができるため、Yes を出力します。
- まず、A の 0 である要素を下記の通りに置き換える。
9 6 8 5 4 4 3 1 3
- 2 列目と 3 列目を入れ替える。その結果、A は下記の通りとなる。
9 8 6 5 4 4 3 3 1
- 1 行目と 3 行目を入れ替える。その結果、A は下記の通りとなる。
3 3 1 5 4 4 9 8 6
- 1 列目と 3 列目を入れ替える。その結果、A は下記の通りとなり、問題文中の条件を満たすようになる。
1 3 3 4 4 5 6 8 9
入力例 2
2 2 2 1 1 2
出力例 2
No
どのように操作を行っても A が問題文中の条件を満たすようにすることはできないため、No を出力します。
Score : 500 points
Problem Statement
You are given a matrix A whose elements are non-negative integers. For a pair of integers (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, let A_{i, j} denote the element at the i-th row and j-th column of A.
Let us perform the following procedure on A.
- First, replace each element of A that is 0 with an arbitrary positive integer (if multiple elements are 0, they may be replaced with different positive integers).
-
Then, repeat performing one of the two operations below, which may be chosen each time, as many times as desired (possibly zero).
- Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq H and swap the i-th and j-th rows of A.
- Choose a pair of integers (i, j) such that 1 \leq i \lt j \leq W and swap the i-th and j-th columns of A.
Determine whether A can be made to satisfy the following condition.
- A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}.
-
In other words, for every two pairs of integers (i, j) and (i', j') such that 1 \leq i, i' \leq H and 1 \leq j, j' \leq W, both of the following conditions are satisfied.
- If i \lt i', then A_{i, j} \leq A_{i', j'}.
- If i = i' and j \lt j', then A_{i, j} \leq A_{i', j'}.
Constraints
- 2 \leq H, W
- H \times W \leq 10^6
- 0 \leq A_{i, j} \leq H \times W
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
H W
A_{1, 1} A_{1, 2} \ldots A_{1, W}
A_{2, 1} A_{2, 2} \ldots A_{2, W}
\vdots
A_{H, 1} A_{H, 2} \ldots A_{H, W}
Output
If A can be made to satisfy the condition in the problem statement, print Yes; otherwise, print No.
Sample Input 1
3 3 9 6 0 0 4 0 3 0 3
Sample Output 1
Yes
One can perform the operations as follows to make A satisfy the condition in the problem statement, so you should print Yes.
- First, replace the elements of A that are 0, as shown below:
9 6 8 5 4 4 3 1 3
- Swap the second and third columns. Then, A becomes:
9 8 6 5 4 4 3 3 1
- Swap the first and third rows. Then, A becomes:
3 3 1 5 4 4 9 8 6
- Swap the first and third columns. Then, A becomes the following and satisfies the condition in the problem statement.
1 3 3 4 4 5 6 8 9
Sample Input 2
2 2 2 1 1 2
Sample Output 2
No
There is no way to perform the operations to make A satisfy the condition in the problem statement, so you should print No.