AT_abc213_c [ABC213C] 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$，用空格隔开。

输入输出样例 #1

输入 #1

4 5 2
3 2
2 5

输出 #1

2 1
1 2

输入输出样例 #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

说明/提示

限制条件

• $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*

写有 $1$ 的卡片在上数第 $2$ 行、左数第 $1$ 列，写有 $2$ 的卡片在上数第 $1$ 行、左数第 $2$ 列。

由 ChatGPT 4.1 翻译