#2122. 无处安放

    ID: 2122 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest301来源:qoj.ac数据:公开样例贪心二分答案

无处安放

无处安放

题目描述

第一试无处安放(nowhere) IOI 2019 中国国家队选拔 无处安放(nowhere) .这.是.一.道.提.交.答.案.题。 【题目背景】 寂寥深夜,朦朦胧胧的月光为一切都笼上一层轻纱,你漫步在幽径,时而低头沉 吟,时而凝望星空,只独孤与彷徨作伴,哪怕只言片语却也无人倾诉,万千思绪伴着你 炽热的心,随风而动,无处安放· · · · · · 【题目描述】 你整理出了n 条思绪,它们在你的心中是一个个矩形ri,你想要在心中用一个大 矩形R 安放它们,也就是将ri 放置在R 内部。为了保护这些思绪,它们安放的位置不 能与其他思绪有重合部分,并且四条边要平行或垂直于R 的边。两个思绪有重合部分, 指它们安放位置的重合面积大于零。 你有两种安放方式:

  1. 将n 条思绪全部安放进R 中,希望令R 的面积尽量小。
  2. 固定R 的大小,希望将尽量多的思绪安放进R 中。 现在我已知晓你整理好的思绪,为你选择了安放的方式,我想知道你心中最好的安 放方案,请你告诉我。 【输入格式】 输入文件nowhere1.in ∼nowhere10.in 已在试题目录下。 对于每组输入数据: 第一行两个整数type, n,分别表示安放方式与思绪的个数。 若type = 2,第二行两个整数W, H,表示R 的边长。 接下来n 行每行两个整数wi, hi,表示第i 个思绪即ri 的边长。 同一行中输入的整数均以一个空格分隔开。 【输出格式】 将输入文件对应的答案,输出到nowhere1.out ∼nowhere10.out 中。 为了方便,若R 的边长为W, H,我们将安放方案视作一个(0, 0) ∼(W, H) 的直角 坐标系。注意对于type = 2 的测试点,你应按输入,将其视作(0, 0) ∼(W, H) 的坐标系, 而不是(0, 0) ∼(H, W) 的坐标系。 输出共有n 行,每行一或四个整数,描述第i 个思绪即ri 的放置方案。 每行第一个整数ci,其中ci = 1 表示ri 被安放在R 中;ci = 0 表示ri 未被安放在 R 中。 第7 页 共9 页 第一试无处安放(nowhere) IOI 2019 中国国家队选拔 若ci = 1, 则该行接下来应输出三个整数xi, yi, diri。若diri = 0,则ri 放置在 (xi, yi) ∼(xi +wi, yi +hi) 的矩形范围内;若diri = 1,则ri 放置在(xi, yi) ∼(xi +hi, yi +wi) 的矩形范围内。 请注意确保你的输出格式正确,且ci, diri ∈{0, 1}。对于type = 1 的测试点,所有 ci 均应为1。 同一行中输出的整数应以一个空格分隔开。 【样例1 输入】 1 3 1 1 1 1 2 1 【样例1 输出】 1 0 0 0 1 0 1 0 1 1 0 1 【样例2 输入】 2 4 2 2 1 1 1 1 2 1 2 1 【样例2 输出】 1 0 0 0 1 0 1 0 1 1 0 1 0 【评分方式】 评分准则nowhere1.ans ∼nowhere10.ans 已放在试题目录下。 第8 页 共9 页 第一试无处安放(nowhere) IOI 2019 中国国家队选拔 每个测试点设置了10 个评分参数a1, a2, · · · , a10。若选手输出不合法,则得零分。 否则,对于安放方式1,令val 为R 的面积,若val ≤ai,则你可获得i 分;对于安放方 式2,令val 为安放到R 中的思绪个数,若val ≥ai 则你可获得i 分。满足多个得分条 件,测试点得分取最高者。 【提示】 试题目录下提供有checker 工具,用于检测你的输出文件。 使用它的方法是,在终端中运行 ./checker <case_number> 其中<case_number> 是测试数据的编号,例如 ./checker 7 将测试nowhere7.out 是否可以接受。 请保存备份好下发的in 与ans 文件,不要随意更改,防止checker 出现不可预知 的错误。 第9 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

1 8
2 10
2 10
4 8
8 4
2 6
2 6
8 4
4 2
232 220 210 200 194 186 174 168 168 168

样例 2

2 12
17 13
5 4
4 8
8 3
4 4
1 5
6 3
1 1
2 13
6 4
4 7
3 4
5 3
3 4 5 6 7 8 9 10 11 12