레이팅 미적용농부 존은 지게차 자격증을 따기 위해 훈련 중이다! 훈련의 일환으로, 그는 오래된 창고에서 \(1\)부터 \(N\)까지 편리하게 번호가 붙은 \(N\) (\(1 \le N \le 10^5\))개의 상자를 치워야 한다.
상자들은 2차원 평면 위의 축에 평행한 직사각형으로 모델링할 수 있으며, \(+x\) 방향이 동쪽이고 \(+y\) 방향이 북쪽이다. 상자 \(i\)의 남서쪽 모서리는 \((x_{i1},y_{i1})\), 북동쪽 모서리는 \((x_{i2},y_{i2})\)에 있다. 모든 좌표는 \([1, 2N]\) 범위의 정수이며, 서로 다른 두 직사각형의 어떤 두 모서리도 같은 \(x\) 또는 \(y\) 좌표를 공유하지 않는다. 모든 상자는 넓이가 0이 아니며, 어떤 두 상자도 겹치지 않는다.
농부 존은 창고의 남서쪽 입구를 통해 상자를 하나씩 빼낼 계획이다. 하지만 지게차의 물리적 한계 때문에, 어떤 상자의 북동쪽 모서리보다 남쪽인 동시에 서쪽에 다른 상자의 일부라도 놓여 있으면 그 상자를 빼낼 수 없다.
\(N=4\)인 예시가 아래에 나와 있다. 상자 \(4\)를 빼내려면 음영 처리된 영역에 다른 상자가 없어야 한다. 상자 \(2\)와 \(3\)은 상자 \(4\)를 빼내는 것을 막지만, 상자 \(1\)은 그렇지 않다.
농부 존이 모든 상자를 빼내는 방법을 결정하도록 도와라! 코드는 정수 플래그 \(M\)으로 정의되는 두 가지 서로 다른 모드로 동작해야 한다.
- 모드 1 (\(M = 1\)): 유효한 상자 제거 순서를 나타내는 \(1, \dots, N\)의 순열을 생성한다. 유효한 순서가 여러 개라면 아무거나 찾으면 된다. 그러한 순서가 항상 존재함을 증명할 수 있다.
- 모드 2 (\(M = 2\)): 각 \(k = 1, \dots, N\)에 대해, 상자 \(1, \dots, k - 1\)이 이미 제거된 상태에서 농부 존이 상자 \(k\)를 제거할 수 있으면 \(\texttt{1}\)을, 아니면 \(\texttt{0}\)을 출력한다.
Problem credits: Austin Geng
SCORING
- 입력 3-5: \(M = 1\), \(N\le 1000\).
- 입력 6: \(M = 2\), \(N \le 1000\).
- 입력 7-13: \(M = 1\), 추가 제약 없음.
- 입력 14-16: \(M = 2\), 추가 제약 없음.
Problem credits: Austin Geng
각 입력은 \(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\)이면, 각 \(k = 1, \dots, N\)에 대한 답을 나타내는 \(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 41 3 2 4
2 3 1The 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
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 41011
011For the first test case, box \(2\) is blocked by box \(3\), so Farmer John cannot
remove it before removing box \(3\).
riseoj 작성
출처 올림피아드 > USACO > 2024-2025 > US Open > Platinum