Sorting a Matrix

AtCoder

IDabc277_f

Time3000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

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

Input #2

2 2
2 1
1 2

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`.

API Response (JSON)

{
  "problem": {
    "name": "Sorting a Matrix",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc277_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments