Reorder Cards

题目描述

我们有一个由 $H$ 行 $W$ 列组成的矩阵，共 $HW$ 张卡片。
对于每个 $i=1,\ldots,N$，位于自上而下第 $A_i$ 行、自左而右第 $B_i$ 列的卡片上写有数字 $i$。其余 $HW-N$ 张卡片上没有任何字迹。 只要可能，我们就重复对这些卡片执行下面两种操作。

如果存在一行没有编号的卡片，则移除该行中的所有卡片，并通过向上移动其余卡片来填补空隙。 如果存在一列没有编号的卡片，则移除该列中的所有卡片，并通过向左移动其余卡片来填补空隙。

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

输入格式

输入按照以下格式从标准输入给出： $H$ $W$ $N$ $A_1$ $B_1$ $\vdots$ $A_N$ $B_N$

输出格式

输出 $N$ 行。 如果在过程结束后编号为 $i$ 的卡片位于自上而下第 $C_i$ 行、自左而右第 $D_i$ 列，则第 $i$ 行应包含 $C_i$ 和 $D_i$，二者之间用一个空格隔开。

4 5 2
3 2
2 5

2 1
1 2

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

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

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

提示

$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)$ 都是不同的。 输入中的所有值均为整数。用 $*$ 表示没有字迹的卡片。初始的卡片排列为：

在过程结束后，它们将被排列为：

这里，标有 $1$ 的卡片位于自上而下第 $2$ 行、自左而右第 $1$ 列，标有 $2$ 的卡片位于自上而下第 $1$ 行、自左而右第 $2$ 列。

标签: AtCoder|abc213C

来源

AtCoder|abc213C