#PQJ301x4473. QOJ 301_4473

    ID: 2888 传统题 10000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTS 2019贪心二分答案

QOJ 301_4473

第一试无处安放(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 页