← 返回题目列表

AtCoder · joisc2021_k

J. 事件跳跃 2

中文机器翻译题面 查看原题

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

イベント巡り 2 (Event Hopping 2) - 原题 PDF 第 1 页
原题PDF第1页
イベント巡り 2 (Event Hopping 2) - 原题 PDF 第 2 页
原题PDF第2页
イベント巡り 2 (Event Hopping 2) - 原题 PDF 第 3 页
原题PDF第3页
イベント巡り 2 (Event Hopping 2) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                Contest Day 4 – Event Hopping 2

         イベント巡り2 (Event Hopping 2)



  IOI 公園ではこれからN 個のイベントが行われる.これらのイベントには1 からN までの番号が付けら
れている.イベントi (1 ≦i ≦N) は時刻Li + 0.1 から時刻Ri −0.1 まで開催される.ここでLi とRi は整数

である.

  JOI 君はこの中からちょうどK 個のイベントに参加することにした.ただし,各イベントに途中から参加

したり,途中で抜けたりすることはできない.移動にかかる時間は考慮しなくてよい.

  JOI 君はなるべく番号が小さいイベントに参加したい.厳密には,JOI 君が参加するK 個のイベントの番
号をa1, . . . , aK (1 ≦a1 < · · · < aK ≦N) としたとき,数列(a1, . . . , aK) が辞書順で最小となるようにしたい.
ただし,(a1, . . . , aK) が(b1, . . . , bK) より辞書順で小さいとは,あるj (1 ≦j ≦K) が存在して「1 ≦ℓ≦j −1
に対しaℓ= bℓ」かつ「a j < b j」を満たすことである.
 イベントの情報とJOI 君が参加するイベントの個数が与えられたとき,JOI 君がK 個のイベントに参加

できるかを判定し,参加できる場合はJOI 君が参加するK 個のイベントを求めるプログラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N K

      L1 R1
                                 ...

     LN RN


出力

 K 個のイベントに参加することが不可能ならば,標準出力に-1 を1 行で出力せよ.

 K 個のイベントに参加することが可能ならば,標準出力にK 行で出力せよ.JOI 君が参加するK 個のイ
ベントの番号をa1, . . . , aK (1 ≦a1 < · · · < aK ≦N) として,j 行目(1 ≦j ≦K) にはaj を出力せよ.ただし,
数列(a1, . . . , aK) は辞書順で最小でなければならない.





                     イベント巡り2– 1 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                Contest Day 4 – Event Hopping 2



制約

    • 1 ≦N ≦100 000.

    • 1 ≦K ≦N.
    • 1 ≦Li < Ri ≦1 000 000 000 (1 ≦i ≦N).


小課題

    1. (7 点) Li ≦Li+1 (1 ≦i ≦N −1).
    2. (1 点) N ≦20.

    3. (31 点) N ≦3 000.

    4. (61 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   5 4                            1

   1 3                            3

   2 5                            4

   8 9                            5

   6 8

   10 15

 ちょうど4 個のイベントに参加する方法は,次の2 通りである.

    • イベント1, 3, 4, 5 に参加する.

    • イベント2, 3, 4, 5 に参加する.

 数列(1, 3, 4, 5) は数列(2, 3, 4, 5) より辞書順で小さいので,1, 3, 4, 5 を出力する.





                     イベント巡り2– 2 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                       Spring Training Camp/Qualifying Trial

                                                March 20–23, 2021 (Komaba, Tokyo)


                                                              Contest Day 4 – Event Hopping 2


 入力例2              出力例2

 4 3                            -1

 1 4

 3 5

 4 9

 7 10

どのように選んでもちょうど3 個のイベントに参加することはできないので,-1 を出力する.


 入力例3              出力例3

 10 6                           1

 77412002 93858605              2

 244306432 318243514            4

 280338037 358494212            6

 439397354 492065507            7

 485779890 529132783            8

 571714810 632053254

 659767854 709114867

 718405631 733610573

 786950301 815106357

 878719468 899999649

この入力例はすべての小課題の制約を満たす.





                    イベント巡り2– 3 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                      Spring Training Camp/Qualifying Trial

                                               March 20–23, 2021 (Komaba, Tokyo)


                                                             Contest Day 4 – Event Hopping 2


入力例4              出力例4

20 16                          1

250732298 258217736            2

26470443 34965880              4

252620676 260043105            5

692063405 697656580            6

497457675 504191511            7

391372149 397942668            8

858168758 867389085            9

235756850 241022021            10

585764751 593366541            11

207824318 217052204            12

661682908 671226688            13

886273261 892279963            14

770109416 778960597            15

264372562 270395107            16

176883483 186662376            17

509929119 519063796

109491630 118520141

162731982 168101507

662727316 668317158

757072772 765493222





                   イベント巡り2– 4 / 4