102775: [AtCoder]ABC277 F - Sorting a Matrix

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

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.

Input

题意翻译

给定一个 $H \times W$ 的矩阵,其中第 $i$ 行第 $j$ 列的数字为 $A_{i,j}$,如果 $A_{i,j}=0$,那么你需要将其替换为任意正整数。 你现在有两种操作: - 选择两行 $i,j$,交换这两行的数字。 - 选择两列 $i,j$,交换这两列的数字。 你希望交换之后满足 $A_{1,1} \leq A_{1,2} \leq A_{1,3} \leq \dots \leq A_{1,W} \leq A_{2,1} \leq \dots \leq A_{2,W} \leq \dots \leq A_{H,W}$。 如果存在至少一种替换数字的方案和操作方案,输出 `Yes`,否则输出 `No`。

Output

分数:500分

问题描述

给你一个矩阵$A$,其元素为非负整数。对于一对整数$(i, j)$,满足$1 \leq i \leq H$和$1 \leq j \leq W$,记$A_{i, j}$表示矩阵$A$的第$i$行第$j$列的元素。

在$A$上执行以下操作。

  • 首先,将矩阵$A$中的每个$0$元素替换为任意一个正整数(如果多个元素为$0$,可以替换成不同的正整数)。
  • 然后,按需求重复执行以下两个操作之一(可以任意选择),次数任意(包括$0$次)。

    • 选择一对整数$(i, j)$,满足$1 \leq i \lt j \leq H$,将矩阵$A$的第$i$行和第$j$行交换。
    • 选择一对整数$(i, j)$,满足$1 \leq i \lt j \leq W$,将矩阵$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}$。
  • 换句话说,对于任意两对整数$(i, j)$和$(i', j')$,满足$1 \leq i, i' \leq H$和$1 \leq j, j' \leq W$,都满足以下两个条件。

    • 如果$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
  • 交换第二列和第三列。然后,$A$变为:
9 8 6
5 4 4
3 3 1
  • 交换第一行和第三行。然后,$A$变为:
3 3 1
5 4 4
9 8 6
  • 交换第一列和第三列。然后,$A$变为以下形式,满足题目描述中的条件。
1 3 3
4 4 5
6 8 9

样例输入 2

2 2
2 1
1 2

样例输出 2

No

无法通过操作使$A$满足题目描述中的条件,所以应该输出No

加入题单

上一题 下一题 算法标签: