[CTS2019] 无处安放

题目背景

寂寥深夜,朦朦胧胧的月光为一切都笼上一层轻纱,你漫步在幽径,时而低头沉 吟,时而凝望星空,只独孤与彷徨作伴,哪怕只言片语却也无人倾诉,万千思绪伴着你炽热的心,随风而动,无处安放……

题目描述

你整理出了 $n$ 条思绪,它们在你的心中是一个个矩形 $r_i$,你想要在心中用一个大矩形 $R$ 安放它们,也就是将 $r_i$ 放置在 $R$ 内部。为了保护这些思绪,它们安放的位置不能与其他思绪有重合部分,并且四条边要平行或垂直于 $R$ 的边。两个思绪有重合部分,指它们安放位置的重合面积大于零。 你有两种安放方式: 1. 将 $n$ 条思绪全部安放进R 中,希望令 $R$ 的面积尽量小。 2. 固定 $R$ 的大小,希望将尽量多的思绪安放进 $R$ 中。 现在我已知晓你整理好的思绪,为你选择了安放的方式,我想知道你心中最好的安放方案,请你告诉我。

输入输出格式

输入格式


第一行两个整数 $type, n$,分别表示安放方式与思绪的个数。 若 $type = 2$,第二行两个整数 $W, H$,表示 $R$ 的边长。 接下来 $n$ 行每行两个整数 $w_i, h_i$,表示第 $i$ 个思绪即 $r_i$ 的边长。 同一行中输入的整数均以一个空格分隔开。

输出格式


为了方便,若 $R$ 的边长为 $W, H$,我们将安放方案视作一个 $(0, 0)\sim(W, H)$ 的直角坐标系。注意对于 $type = 2$ 的测试点,你应按输入,将其视作 $(0, 0)\sim(W, H)$ 的坐标系,而不是 $(0, 0) \sim (H, W)$ 的坐标系。 输出共有 $n$ 行,每行一或四个整数,描述第 $i$ 个思绪即 $r_i$ 的放置方案。 每行第一个整数 $c_i$,其中 $c_i = 1$ 表示 $r_i$ 被安放在 $R$ 中;$c_i = 0$ 表示 $r_i$ 未被安放在 $R$ 中。 若 $c_i = 1$, 则该行接下来应输出三个整数 $x_i$, $y_i$, $d_{ir_i}$。若 $d_{ir_i} = 0$,则 $r_i$ 放置在 $(x_i, y_i)\sim(x_i + w_i, y_i + h_i)$ 的矩形范围内;若 $d_{ir_i} = 1$,则 $r_i$ 放置在 $(x_i, y_i)\sim(x_i + h_i, y_i + w_i)$ 的矩形范围内。 请注意确保你的输出格式正确,且 $c_i, d_{ir_i} \in \{0, 1\}$。对于 $type = 1$ 的测试点,所有 $c_i$ 均应为 $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

说明

#### 评分方式 每个测试点设置了 $10$ 个评分参数 $a_1, a_2, ..., a_{10}$。若选手输出不合法,则得零分。 否则,对于安放方式 $1$,令 $val$ 为 $R$ 的面积,若 $val \leq a_i$,则你可获得 $i$ 分;对于安放方式 $2$,令 $val$ 为安放到 $R$ 中的思绪个数,若 $val \geq a_i$ 则你可获得 $i$ 分。满足多个得分条件,测试点得分取最高者。