| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 130 | 74 | 68 | 59.130% |
재현이는 다음 두 종류의 쿼리를 처리하는 프로그램을 작성했다.
1 $l$ $r$: 새로운 구간 $\left( l,r \right)$을 구간 모음에 추가한다.2 $a$ $b$: 구간 모음에 $a$번째로 추가된 구간과 $b$번째로 추가된 구간이 연결되어 있으면 1, 없으면 0을 출력한다.처음 구간 모음은 비어 있으며, 쿼리로 주어지는 구간은 중복될 수 있다.
어떤 구간 $\left( l_i,r_i \right)$과 구간 $\left( l_j,r_j \right)$에 대해 $l_i<c<r_i$이고 $l_j<c<r_j$를 만족하는 실수 $c$가 존재하면 이 두 구간은 연결되어 있으며, 이 연결 관계는 전이적으로 확장된다. 즉, 구간 $X$와 $Y$가 연결되어 있고 $Y$와 $Z$가 연결되어 있으면 $X$와 $Z$도 연결되어 있다.
재현이는 이 프로그램을 디버깅하던 중, 쿼리들이 적혀 있는 파일을 삭제해 버렸다. 다행히 각 쿼리가 몇 개씩 있는지와 쿼리 실행 결과는 알 수 있었다.
각 쿼리의 개수와 쿼리의 실행 결과가 주어졌을 때, 그 결과를 만들 수 있는 쿼리들을 복원해 보자.
첫 번째 줄에 1번 쿼리의 개수 $N(2\le N\le 100\, 000)$과 2번 쿼리의 개수 $M(1\le M\le 100\, 000)$이 공백으로 구분되어 주어진다.
두 번째 줄부터 $M$줄에 걸쳐 2번 쿼리에 대한 결과 0 혹은 1이 한 줄에 하나씩 주어진다.
만약 주어진 결과를 만들 수 있다면 첫 번째 줄에 1을, 없다면 -1을 출력한다.
만약 주어진 결과를 만들 수 있다면 두 번째 줄부터 $N+M$줄에 걸쳐 한 줄에 하나씩 쿼리들을 출력한다.
1번 쿼리의 $l$과 $r$은 $-10^9\le l<r\le 10^9$인 정수여야 하며, 2번 쿼리의 $a$와 $b$는 각각 이전에 출력된 1번 쿼리의 개수 이하의 정수이며, $a\ne b$여야 한다.
3 3 1 1 1
1 1 -1 3 1 0 4 1 1 5 2 1 2 2 2 3 2 3 1
3 3 0 0 0
1 1 -1 0 1 0 1 1 1 2 2 1 2 2 2 3 2 3 1
2 2 0 1
-1
University > 고려대학교 > 고려대학교 프로그래밍 경시대회 > 2025 고려대학교 프로그래밍 경시대회 (KCPC) > Div. 1 H번