| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 118 | 1 | 1 | 11.111% |
It's time for the Shumen Music Festival! The lineup consists of N performers, each of whom will give two concerts. The time period of the first concert by performer i is [ai; bi], while the time period of the second one is [ci; di].
Alice is wondering which concerts to go to. Because she likes all music genres, she would like to attend at least one concert by each performer. The problem is, there could be multiple concerts taking place at the same time but Alice could only attend at most one of them. That's why she needs your help!
She is asking you to write program that selects one concert by each performer in such a way, that no two of the selected concerts overlap if it is possible, or determines that this is impossible. Two concerts that are at time periods [si; ei] and [sj; ej] overlap, if there exists a moment in time t so that it meets the conditions: si ≤ t ≤ ei and sj ≤ t ≤ ej.
The first line of the standard input consists of a single integer N - the number of performers. N lines follow, describing the time periods of the concerts: line i+1 consists of the moments of time, integer ai, bi, ci, and di for the i-th performer.
The first line of the standard output must be a single word: "Yes", if it's possible to satisfy Alice's requirements, and "No", otherwise. If your program outputs "Yes", there should be N more lines, indicating the concerts Alice should attend: Line i+1 should contain "1" if Alice should attend the first concert of the performer with number i, or "2" if Alice should go to the second concert of the performer with number i. In case there are multiple possible solutions, you can print any one of them.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | N ≤ 20 |
| 2 | 15 | N ≤ 4·103, ai = bi and ci = di for every i |
| 3 | 32 | N ≤ 4·103 |
| 4 | 43 | N ≤ 105 |
3 0 0 1 6 2 2 3 4 1 3 5 5
Yes 1 2 2
3 0 0 1 6 2 2 3 4 0 0 1 3
No
4 2 2 3 3 0 0 4 4 0 0 1 1 1 1 2 2
Yes 1 2 1 1
10 21 22 33 35 16 18 26 27 9 10 14 23 0 1 15 34 12 17 19 32 4 28 30 38 5 6 13 31 2 3 20 37 24 25 29 36 7 8 11 39
Yes 1 2 1 1 1 2 1 1 1 1