結果

問題 No.2804 Fixer And Ratism
コンテスト
ユーザー D M
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0