#PU1524. USACO 2025 US Open Contest, Platinum — Problem 1. Forklift Certified

USACO 2025 US Open Contest, Platinum — Problem 1. Forklift Certified

USACO 2025 US Open Contest, Platinum — Problem 1. Forklift Certified

题目描述

Farmer John is training to become forklift certified! As part of his training, he needs to clear NN (1≤N≤1051 \le N \le 10^5) boxes, conveniently labeled 11 through NN, from an old warehouse. The boxes can be modeled as axis-aligned rectangles in a 2-dimensional plane, where the +x+x-direction is east and the +y+y-direction is north. Box ii has its southwest corner at (xi1,yi1)(x_{i1},y_{i1}) and its northeast corner at (xi2,yi2)(x_{i2},y_{i2}). All coordinates are integers in the range [1,2N][1, 2N], and no two corners from two different rectangles share the same xx or yy coordinate. All boxes have a non-zero area, and no two boxes intersect. Farmer John plans to remove the boxes one at a time out of the southwest entrance of the warehouse. However, he can only remove a box if no part of any other box lies both south and west of the box's northeast corner due to physical limitations of the forklift. An example with N=4N=4 is shown below. To remove box 44, there cannot be any other boxes in the shaded region. Boxes 22 and 33 prevent box 44 from being removed, but box 11 does not. Help Farmer John decide how to remove all the boxes! Your code should operate in two separate modes, defined by an integer flag MM: Mode 1 (M=1M = 1): Generate a permutation of 1,…,N1, \dots, N specifying a valid box removal order. If there are multiple valid orders, find any. It can be proven that such an order always exists. Mode 2 (M=2M = 2): For each k=1,…,Nk = 1, \dots, N, output 1\texttt{1} if Farmer John can remove box kk if boxes 1,…,k−11, \dots, k - 1 have already been removed, and 0\texttt{0} otherwise.

输入格式

Each input consists of TT (1≤T≤101 \le T \le 10) independent test cases. It is guaranteed that the sum of all NN within each input does not exceed 5⋅1055 \cdot 10^5. The first line of input contains TT and MM. (Note that MM is the same for each test case.) Each test case is then formatted as follows: The first line contains a single integer NN. Each of the next NN lines contains four space-separated integers xi1,yi1,xi2,yi2x_{i1}, y_{i1}, x_{i2}, y_{i2}: the locations of the southwest and northeast corners of box ii.

输出格式

For each test case: If M=1M = 1, output a single line with NN space-separated integers, where the jj-th integer is the label of the jj-th box to remove. If M=2M = 2, output a single line with a binary string of NN characters specifying the answer for each k=1,…,Nk = 1, \dots, N.

数据范围

Inputs 3-5: M=1M = 1, N≤1000N\le 1000.

样例

样例 1

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
The first test case corresponds to the $N = 4$ example above. Box $1$ is not
blocked by anything, box $3$ is blocked by box $1$, box $2$ is blocked by box
$3$, and box $4$ is blocked by boxes $2$ and $3$.

样例 2

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
For the first test case, box $2$ is blocked by box $3$, so Farmer John cannot
remove it before removing box $3$.