No.2804 Fixer And Ratism
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 96
作問者 :
primenumber11
/ テスター :
hirayuu_yc
highlighter
Magentor
kinugoshi8928
keisuke6
silv723
Yoyoyo8128
zeta7532
fact493
タグ : / 解いたユーザー数 96
作問者 :
![highlighter](https://pbs.twimg.com/profile_images/1707374069132439552/b_BWx6c8.png)
![Magentor](https://pbs.twimg.com/profile_images/1715389554197495808/7HlNzj_p.jpg)
![keisuke6](https://pbs.twimg.com/profile_images/1675785204974354432/k3Bvkvyj.jpg)
![fact493](https://pbs.twimg.com/profile_images/1641449306531192836/GjfyenV1.jpg)
問題文最終更新日: 2024-07-12 20:52:53
問題文
競プロ部には $100$ 人の部員がおり、競プロ部の部室には $10^9$ 台のパソコンがあります。時刻 $0$ の時点では、そのうち $N$ 台のパソコンが使用可能です。
出来事が $Q$ 個入力されます。$i \ (1 \leq i \leq Q)$ 番目のクエリは、時刻 $i$ に起きた出来事を表します。クエリの入力は、次のような形式で与えられます。
- クエリ1:
1 s r
の形式で与えられる。レート $r$ の部員 $s$ が部室に来る。 - クエリ2:
2 x
の形式で与えられる。$x$ 個のパソコンが使用不可能になる。 - クエリ3:
3 s x
の形式で与えられる。部室にいる部員 $s$ が $x$ 個のパソコンを使用可能にする。
パソコンは、次のような順番で、現在使用可能なパソコンの台数に対し $1$ 人 $1$ 台使います。
- パソコンを $1$ 台でも使用可能にしたことがある人の中でレートが高い順
- 上に当てはまる人全員が使ってもまだ使える台がある場合、上に当てはまらない人の中でレートが高い順
使用可能なパソコンの台数より現在部室にいる部員の人数の方が多くなった場合、上の順番によってパソコンを使える部員を決めて、使えない部員は即座に部室を出て帰ります。
一度帰った人が再度部室に来ることはありません。
帰った人の名前を、帰った時刻が早い人から順に $1$ 人 $1$ 行ずつ全て出力してください。
複数人が同時に帰った場合は、同時に帰った人々の名前をレートが低い人から順に出力してください。
制約
- $1 \leq N \leq 100$
- $1 \leq Q \leq 100000$
- $0 \leq r \leq 4000$
- $1 \leq x \leq 10$
- $1 \leq |s| \leq 100$
- $s$ は英小文字からなる
- $s$ 以外の入力はすべて整数である
- 部員の名前は高々 $100$ 種類である
- 部員の名前とレートはそれぞれ相異なる
- 使用可能なパソコンの台数は常に $1$ 以上である
- クエリ1で与えられる部員はまだ部室に来ていない
- クエリ3で与えられる部員は部室にいる
入力
$N\ Q$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$
各クエリは次のように与えられます。
1 $s$ $r$ 2 $x$ 3 $s$ $x$
出力
帰らなければならなくなった人の名前を問題文で説明した順に $1$ 人 $1$ 行ずつ全て出力してください。
サンプル
サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。