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

AT_agc017_e.[AGC017E] Jigsaw

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

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

题目描述

有 NN 个特殊的拼图块。每个拼图块由三个宽度为 11、高度不小于 11 的矩形拼接而成。第 ii 个拼图块的构造如下：

  • 以高度为 HH 的矩形块为中间部分，将高度为 AiA_i 的矩形块连接在左侧，高度为 BiB_i 的矩形块连接在右侧。其中，左侧矩形块底边比中间矩形块底边高 CiC_i，右侧矩形块底边比中间矩形块底边高 DiD_i。

Sune君想把这些拼图块放在一个边长为 1010010^{100} 的正方形桌子上。此时需要满足以下条件：

  • 必须把所有拼图块都放在桌子上。
  • 每个拼图块的中间部分底边都要与桌子的前边缘接触。
  • 左右两侧的矩形块的底边要么与桌子的前边缘接触，要么与其他某个拼图块的某部分的上边缘完全接触。
  • 不能旋转或翻转拼图块。

请判断是否存在一种满足条件的排放方法。

输入格式

输入按以下格式由标准输入给出：

NN HH A1A_1 B1B_1 C1C_1 D1D_1 A2A_2 B2B_2 C2C_2 D2D_2 : ANA_N BNB_N CNC_N DND_N

输出格式

如果存在一种满足条件的拼图块排列方式，输出 YES；否则输出 NO。

输入输出样例

  • 输入#1

    3 4
1 1 0 0
2 2 0 1
3 3 1 0

    输出#1

    YES

  • 输入#2

    4 2
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1

    输出#2

    NO

  • 输入#3

    10 4
1 1 0 3
2 3 2 0
1 2 3 0
2 1 0 0
3 2 0 2
1 1 3 0
3 2 0 0
1 3 2 0
1 1 1 3
2 3 0 0

    输出#3

    YES

说明/提示

范围

  • 1≤N≤1000001\leq N\leq 100000
  • 1≤H≤2001\leq H\leq 200
  • 1≤Ai≤H1\leq A_i\leq H
  • 1≤Bi≤H1\leq B_i\leq H
  • 0≤Ci≤H−Ai0\leq C_i\leq H-A_i
  • 0≤Di≤H−Bi0\leq D_i\leq H-B_i
  • 所有输入均为整数。

样例解释 1

例如，可以按下图方式进行放置。

由 ChatGPT 5 翻译

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

首页