Forklift Certified

题目描述

Farmer John 正在训练成为叉车认证人员！作为训练的一部分，他需要从一座旧仓库中清除 $N$（$1 \le N \le 10^5$）个箱子，箱子方便地编号为 $1$ 到 $N$。 箱子可建模为二维平面上的轴对齐矩形，其中 $+x$ 方向为东，$+y$ 方向为北。箱子 $i$ 的西南角为 $(x_{i1},y_{i1})$，东北角为 $(x_{i2},y_{i2})$。所有坐标都是 $[1, 2N]$ 范围内的整数，并且任意两个不同矩形的角点不会有相同的 $x$ 或 $y$ 坐标。所有箱子面积非零，且任意两箱子互不相交。 Farmer John 计划从仓库的西南入口一次移走一个箱子。然而，由于叉车的物理限制，他只能在满足以下条件时移走一个箱子：不存在任何其他箱子的任意部分同时位于该箱子东北角的南侧与西侧。 下面展示了一个 $N=4$ 的例子。要移走箱子 $4$，阴影区域内不能有任何其他箱子。箱子 $2$ 和 $3$ 会阻止移走箱子 $4$，但箱子 $1$ 不会。 请帮助 Farmer John 决定如何移走所有箱子！你的代码需要在由整数标志 $M$ 定义的两种独立模式下运行： 模式 1（$M = 1$）： 生成一个 $1, \dots, N$ 的排列，表示一种合法的移箱顺序。若存在多种合法顺序，输出任意一种即可。可以证明这样的顺序总是存在。 模式 2（$M = 2$）： 对每个 $k = 1, \dots, N$，若在箱子 $1, \dots, k - 1$ 已经被移走的情况下 Farmer John 能移走箱子 $k$，输出 $\texttt{1}$，否则输出 $\texttt{0}$。

输入格式

每个输入包含 $T$（$1 \le T \le 10$）组相互独立的测试用例。保证每个输入中所有测试用例的 $N$ 之和不超过 $5 \cdot 10^5$。 输入第一行包含 $T$ 和 $M$。（注意：对每个测试用例，$M$ 都相同。）每个测试用例如下： 第一行包含一个整数 $N$。 接下来 $N$ 行每行包含四个用空格分隔的整数 $x_{i1}, y_{i1}, x_{i2}, y_{i2}$：表示箱子 $i$ 的西南角与东北角的位置。

输出格式

对每个测试用例： 若 $M = 1$，输出一行 $N$ 个用空格分隔的整数，其中第 $j$ 个整数是第 $j$ 个要移走的箱子的编号。 若 $M = 2$，输出一行长度为 $N$ 的二进制字符串，表示对每个 $k = 1, \dots, N$ 的答案。

2 1
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

1 3 2 4
2 3 1

2 2
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

1011
011

提示

第一个测试用例对应上述 $N = 4$ 的例子。箱子 $1$ 不被任何东西阻挡，箱子 $3$ 被箱子 $1$ 阻挡，箱子 $2$ 被箱子 $3$ 阻挡，箱子 $4$ 被箱子 $2$ 和 $3$ 阻挡。 对于第一个测试用例，箱子 $2$ 被箱子 $3$ 阻挡，因此 Farmer John 在移走箱子 $3$ 之前无法移走它。 计分： 输入 3-5：$M = 1$，$N\le 1000$。 输入 6：$M = 2$， $N \le 1000$。 输入 7-13：$M = 1$，无额外限制。 输入 14-16：$M = 2$，无额外限制。 题目来源：Austin Geng

标签: USACO|2025|Platinum

来源

USACO|2025|Platinum