문제
IOI 공원에서 N개의 행사가 곧 열린다.
각 행사는 1번부터 N번까지의 번호가 붙어 있다.
i번째 행사는 Li+0.1초에 시작하여 Ri-0.1초에 끝난다.
준혁이는 정확히 K개의 행사에 참가하려고 한다.
행사 도중 입장하거나, 자리를 떠나는 것은 금지되어 있다.
행사장 사이의 이동시간은 무시한다.
준혁이는 최대한 작은 번호를 가진 행사들을 참가하고 싶다.
자세히는, 준혁이가 참가할 행사들의 번호를 a1, ... , ak라고 하자. (1 <= a1 < ... < ak <= N)
이때, (a1, ... , ak)는 가능한 사전순으로 가장 작은 수열이어야 한다.
K와 행사들의 정보가 주어졌을 때, 준혁이가 K개의 행사를 참가할 수 없는지 판별하고, 있다면 해당 K개의 행사를 출력하여라.
입력
N K
L1 L2
...
LN RN
1 <= N <= 100,000
1 <= K <= N
1 <= Li <= Ri <= 1,000,000,000
출력
준혁이가 K개의 행사에 참가할 수 없을 경우, -1을 출력한다.
이외의 경우, a1, ... , ak를 K개의 줄에 걸쳐 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 7점 | Li <= L(i+1) |
| #2 | 1점 | N <= 20 |
| #3 | 31점 | N <= 3,000 |
| #4 | 61점 | N <= 100,000 |
예제 #1
5 4
1 3
2 5
8 9
6 8
10 15
1
3
4
5
예제 #2
4 3
1 4
3 5
4 9
7 10
-1
예제 #3
10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649
1
2
4
6
7
8
예제 #4
20 16
250732298 258217736
26470443 34965880
252620676 260043105
692063405 697656580
497457675 504191511
391372149 397942668
858168758 867389085
235756850 241022021
585764751 593366541
207824318 217052204
661682908 671226688
886273261 892279963
770109416 778960597
264372562 270395107
176883483 186662376
509929119 519063796
109491630 118520141
162731982 168101507
662727316 668317158
757072772 765493222
1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17
로그인해야 코드를 작성할 수 있어요.