結果

問題 No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
コンテスト
ユーザー rpy3cpp
提出日時 2016-10-21 13:13:38
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 637 ms / 4,000 ms
コード長 1,259 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 189 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 41,016 KB
最終ジャッジ日時 2024-11-23 16:45:08
合計ジャッジ時間 18,961 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import collections
import heapq

def read_data():
    N, K = map(int, input().split())
    db = [collections.defaultdict(list) for _ in range(11)]
    for teamID in range(N):
        s, p, u = map(int, input().split())
        db[s][u].append((-p, teamID))
    return N, K, db

def solve(N, K, db):
    ans = []
    counter = [0] * (10**5 + 1)
    for dbs in db[::-1]:
        if not dbs:
            continue
        result = solve_core(dbs, counter)
        ans.extend(result)
        if len(ans) >= K:
            return ans[:K]

def solve_core(dbs, counter):
    ans = []
    que = []
    for univID, lst in dbs.items():
        lst.sort()
        p = -lst[-1][0]
        teamID = lst[-1][1]
        que.append((counter[univID], p, teamID, univID))
        del lst[-1]
    heapq.heapify(que)
    while que:
        counts, p, teamID, univID = que[0]
        ans.append(teamID)
        lst = dbs[univID]
        counter[univID] += 1
        if lst:
            p = -lst[-1][0]
            teamID = lst[-1][1]
            heapq.heapreplace(que, (counts + 1, p, teamID, univID))
            del dbs[univID][-1]
        else:
            heapq.heappop(que)
    return ans

N, K, db = read_data()
ans = solve(N, K, db)
for univ_key in ans:
    print(univ_key)
0