結果
問題 |
No.2804 Fixer And Ratism
|
ユーザー |
|
提出日時 | 2025-02-12 15:36:48 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 3,348 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 76,384 KB |
最終ジャッジ日時 | 2025-02-12 15:37:18 |
合計ジャッジ時間 | 4,173 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 |
ソースコード
import sys def main(): input = sys.stdin.readline N, Q = map(int, input().split()) avail = N # 現在使用可能なパソコンの台数 # 現在部室にいる部員を、名前をキーとして (rating, activated) を保持する辞書 current = dict() # key: name, value: [rating, activated] departures = [] # 退室した部員の記録:各要素は (time, rating, name) for time in range(1, Q+1): query = input().split() typ = int(query[0]) if typ == 1: # クエリ1: "1 s r" 部員 s (レート r) が来る. s = query[1] r = int(query[2]) # 初来室時は activated=False current[s] = [r, False] elif typ == 2: # クエリ2: "2 x" 使用不可能になるパソコン台数 x x = int(query[1]) avail -= x else: # クエリ3: "3 s x" s が x 台のパソコンを使用可能にする s = query[1] x = int(query[2]) avail += x # s がこの操作をすることで,activatedフラグを True に if s in current: current[s][1] = True # クエリ実行後,部室にいる部員数が avail より多いときは退室処理を行う if len(current) > avail: # まず,activated == True の部員(グループA)を抽出し,レート降順に並べる. groupA = [(name, info[0]) for name, info in current.items() if info[1]] groupA.sort(key=lambda x: x[1], reverse=True) # activated == False の部員(グループB)を抽出し,レート降順に並べる. groupB = [(name, info[0]) for name, info in current.items() if not info[1]] groupB.sort(key=lambda x: x[1], reverse=True) remain = [] # まずグループAの全員(もしくは avail 台に収まるだけ)を選ぶ. takeA = min(len(groupA), avail) for i in range(takeA): remain.append(groupA[i][0]) # もしまだパソコンに余裕があればグループBから選ぶ. remainingSlots = avail - takeA for i in range(min(remainingSlots, len(groupB))): remain.append(groupB[i][0]) # 割り当てられなかった部員は退室. # ここで,同じ時刻に複数退室する場合は後でレート昇順で出力するため記録しておく. leave_list = [] for name, info in current.items(): if name not in remain: leave_list.append( (name, info[0]) ) # 同一時刻内では,レートが低い順に出力するのでソート leave_list.sort(key=lambda x: x[1]) for name, rate in leave_list: departures.append((time, rate, name)) del current[name] # 最終的に,全退室記録を「時刻昇順,かつ同時刻ならレート昇順」で出力 departures.sort(key=lambda x: (x[0], x[1])) out_lines = [] for t, rate, name in departures: out_lines.append(name) sys.stdout.write("\n".join(out_lines)) if __name__ == '__main__': main()