AT_abc213_c.[ABC213C] Reorder Cards

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在 $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
```
4 5 2
3 2
2 5
```
输出#1
```
2 1
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 \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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页