题目详情题解（0）讨论（0）提交记录（0）

AT_abc445_d.[ABC445D] Reconstruct Chocolate

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

桌子上放着 NN 块巧克力，每块编号为 i (1≤i≤N)i\ (1 \leq i \leq N)，第 ii 块为高 hih_i、宽 wiw_i 的矩形。

已知这些巧克力块是通过如下操作获得的：

  • 开始时，手上有一块高 HH、宽 WW 的完整巧克力，桌子上还没有放置任何巧克力块。
  • 反复进行如下操作 N−1N-1 次：
    • 将手上的一块巧克力在块的边界处分成两个部分，分割后得到的两块依然是矩形。
    • 把其中一块放在桌子上，手上保留另一块。
  • 最后一步，将手上剩下的那块巧克力也放在桌子上。

请你找出一种方式，将这 NN 块巧克力拼成高 HH、宽 WW 的矩形，满足以下条件：

  • 不同的块之间不能重叠。
  • 不允许旋转巧克力，即对于 h≠wh \neq w，高 hh、宽 ww 的巧克力不能以高 ww、宽 hh 的形式放置。

输入格式

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

H W N h1 w1 h2 w2 … hN wNH\ W\ N\ h_1\ w_1\ h_2\ w_2\ \ldots\ h_N\ w_N

输出格式

对于每一块巧克力 i (1≤i≤N)i\ (1 \leq i \leq N)，设其左上角放置在整个大矩形的第 xix_i 行、第 yiy_i 列（从左上角起，分别从上到下、从左到右计数）。请输出如下格式：

x1 y1 x2 y2 … xN yNx_1\ y_1\ x_2\ y_2\ \ldots\ x_N\ y_N

如果存在多种合法的方案，输出任意一种即可。

输入输出样例

  • 输入#1

    4 6 6
2 2
1 4
3 1
1 2
3 1
4 2

    输出#1

    2 2
4 1
1 1
1 2
1 4
1 5

  • 输入#2

    100 100 20
72 7
4 74
17 67
20 67
96 3
1 95
5 81
87 3
3 87
16 67
95 8
100 2
92 1
3 98
92 5
87 3
1 98
19 67
11 74
87 1

    输出#2

    7 89
90 22
62 22
7 22
4 96
99 1
94 15
7 19
4 9
27 22
4 1
1 99
7 14
1 1
7 9
7 16
100 1
43 22
79 22
7 15

说明/提示

样例解释 1

样例输出展示的拼法如下图所示：

数据范围

  • 1≤H≤1091 \leq H \leq 10^9
  • 1≤W≤1091 \leq W \leq 10^9
  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 1≤hi≤H1 \leq h_i \leq H
  • 1≤wi≤W1 \leq w_i \leq W
  • 保证输入数据是按照题目描述中的方式分割得到的。
  • 所有输入均为整数。

由 ChatGPT 5 翻译

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

首页