102132: [AtCoder]ABC213 C - Reorder Cards

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

Description

Score : $300$ points

Problem Statement

We have $HW$ cards arranged in a matrix with $H$ rows and $W$ columns.
For each $i=1, \ldots, N$, the card at the $A_i$-th row from the top and $B_i$-th column from the left has a number $i$ written on it. The other $HW-N$ cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

  • If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
  • If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

  • $1 \leq H,W \leq 10^9$
  • $1 \leq N \leq \min(10^5,HW)$
  • $1 \leq A_i \leq H$
  • $1 \leq B_i \leq W$
  • All pairs $(A_i,B_i)$ are distinct.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$H$ $W$ $N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

Output

Print $N$ lines.

If, after the end of the process, the card with the number $i$ is at the $C_i$-th row from the top and $D_i$-th column from the left, the $i$-th line should contain $C_i$ and $D_i$ in this order with a space between them.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with $1$ is at the $2$-nd row from the top and $1$-st column from the left, and the card with $2$ is at the $1$-st row from the top and $2$-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

Input

题意翻译

在 $H$ 行 $W$ 列的矩阵中分布着 $N$ 个关键点。现在将所有不包括关键点的行或列全部删除（删除后将相邻的行/列接在一起），求删除之后所有关键点在矩阵中的新位置。 输出时按照关键点的输入顺序输出关键点的新位置。

Output

得分：300分

问题描述

我们有$HW$张卡片，排列成一个具有$H$行和$W$列的矩阵。

对于每个$i=1, \ldots, N$，从顶部算起第$A_i$行、从左部算起第$B_i$列的卡片上写着数字$i$。其他$HW-N$张卡片上什么也没有写。

只要可以，我们就在这些卡片上重复执行以下两种操作。

  • 如果存在一行没有编号的卡片，那么移除该行的所有卡片，并通过将剩余卡片向上移动来填充空白。
  • 如果存在一列没有编号的卡片，那么移除该列的所有卡片，并通过将剩余卡片向左移动来填充空白。

找出上述过程结束后每张编号卡片的位置。可以证明，这些位置是唯一确定的，不依赖于执行操作的顺序。

约束条件

  • $1 \leq H,W \leq 10^9$
  • $1 \leq N \leq \min(10^5,HW)$
  • $1 \leq A_i \leq H$
  • $1 \leq B_i \leq W$
  • 所有$(A_i,B_i)$对都是不同的。
  • 输入中的所有值都是整数。

输入

输入通过标准输入给出，格式如下：

$H$ $W$ $N$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

输出

输出$N$行。

如果，在过程结束后，编号为$i$的卡片位于顶部算起第$C_i$行、左部算起第$D_i$列，那么第$i$行应包含$C_i$和$D_i$，中间用空格隔开。

样例输入1

4 5 2
3 2
2 5

样例输出1

2 1
1 2

让*表示一张什么也没有写的卡片。卡片的初始排列如下：

*****
****2
*1***
*****

过程结束后，它们将排列如下：

*2
1*

在这里，编号为$1$的卡片位于顶部算起第$2$行、左部算起第$1$列，编号为$2$的卡片位于顶部算起第$1$行、左部算起第$2$列。

样例输入2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

样例输出2

1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

Source/Category

加入题单

上一题 下一题 算法标签：