問題一覧 > 通常問題

No.2804 Fixer And Ratism

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 99
作問者 : primenumber11primenumber11 / テスター : hirayuu_ychirayuu_yc highlighterhighlighter MagentorMagentor kinugoshi8928kinugoshi8928 keisuke6keisuke6 silv723silv723 Yoyoyo8128Yoyoyo8128 zeta7532zeta7532 fact493fact493
0 ProblemId : 10890 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-12 20:52:53

問題文

競プロ部には 100100 人の部員がおり、競プロ部の部室には 10910^9 台のパソコンがあります。時刻 00 の時点では、そのうち NN 台のパソコンが使用可能です。

出来事が QQ 個入力されます。i (1iQ)i \ (1 \leq i \leq Q) 番目のクエリは、時刻 ii に起きた出来事を表します。クエリの入力は、次のような形式で与えられます。

  • クエリ1: 1 s r の形式で与えられる。レート rr の部員 ss が部室に来る。
  • クエリ2: 2 x の形式で与えられる。xx 個のパソコンが使用不可能になる。
  • クエリ3: 3 s x の形式で与えられる。部室にいる部員 ssxx 個のパソコンを使用可能にする。

パソコンは、次のような順番で、現在使用可能なパソコンの台数に対し 1111 台使います。

  • パソコンを 11 台でも使用可能にしたことがある人の中でレートが高い順
  • 上に当てはまる人全員が使ってもまだ使える台がある場合、上に当てはまらない人の中でレートが高い順

使用可能なパソコンの台数より現在部室にいる部員の人数の方が多くなった場合、上の順番によってパソコンを使える部員を決めて、使えない部員は即座に部室を出て帰ります。

一度帰った人が再度部室に来ることはありません。

帰った人の名前を、帰った時刻が早い人から順に 1111 行ずつ全て出力してください。

複数人が同時に帰った場合は、同時に帰った人々の名前をレートが低い人から順に出力してください。

制約

  • 1N1001 \leq N \leq 100
  • 1Q1000001 \leq Q \leq 100000
  • 0r40000 \leq r \leq 4000
  • 1x101 \leq x \leq 10
  • 1s1001 \leq |s| \leq 100
  • ss は英小文字からなる
  • ss 以外の入力はすべて整数である
  • 部員の名前は高々 100100 種類である
  • 部員の名前とレートはそれぞれ相異なる
  • 使用可能なパソコンの台数は常に 11 以上である
  • クエリ1で与えられる部員はまだ部室に来ていない
  • クエリ3で与えられる部員は部室にいる

入力

N QN\ Q
query1\text{query}_1
query2\text{query}_2
\vdots
queryQ\text{query}_Q

各クエリは次のように与えられます。

1 ss rr
2 xx
3 ss xx

出力

帰らなければならなくなった人の名前を問題文で説明した順に 1111 行ずつ全て出力してください。

サンプル

サンプル1
入力
1 5
1 fact 2400
3 fact 2
1 kyoproking 3900
1 yoyoyo 1700
1 pura 1100
出力
pura

部員の名前は実在するものとは限りません。

サンプル2
入力
10 3
1 yakisobatabetai 0
2 9
1 yakisobairanai 1
出力
yakisobatabetai
サンプル3
入力
3 11
1 magentor 2000
1 warabi 1650
1 kinugoshi 1400
3 kinugoshi 1
2 3
3 kinugoshi 1
1 zeta 2300
3 zeta 2
1 highlightermath 1700
2 2
1 kyoproking 3900
出力
warabi
magentor
highlightermath
kyoproking

レートが高い人よりパソコンを使用可能にした人の方が優遇されます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。