結果

問題 No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
ユーザー lam6er
提出日時 2025-04-16 16:01:54
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,442 bytes
コンパイル時間 336 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 113,692 KB
最終ジャッジ日時 2025-04-16 16:08:17
合計ジャッジ時間 10,584 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    k = int(data[idx+1])
    idx += 2
    
    heaps = [[] for _ in range(11)]  # S ranges from 0 to 10
    team_univ = []
    
    for team_id in range(n):
        s = int(data[idx])
        p = int(data[idx+1])
        u = int(data[idx+2])
        idx += 3
        team_univ.append(u)
        heapq.heappush(heaps[s], (0, p, team_id))  # (current_count, penalty, team_id)
    
    univ_counts = defaultdict(int)
    result = []
    
    for _ in range(k):
        # Find the highest S with non-empty heap
        selected_s = -1
        for s in range(10, -1, -1):
            if heaps[s]:
                selected_s = s
                break
        if selected_s == -1:
            break  # no more teams, though K <= N
        
        while True:
            current_count, p, team_id = heapq.heappop(heaps[selected_s])
            u = team_univ[team_id]
            if current_count == univ_counts[u]:
                # Select this team
                univ_counts[u] += 1
                result.append(team_id)
                break
            else:
                # Re-insert with updated current_count
                heapq.heappush(heaps[selected_s], (univ_counts[u], p, team_id))
    
    print('\n'.join(map(str, result)))

if __name__ == "__main__":
    main()
0