結果

問題 No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:30:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,360 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,848 KB
実行使用メモリ 124,924 KB
最終ジャッジ日時 2025-03-31 17:31:51
合計ジャッジ時間 13,867 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import heapq
import sys
from collections import defaultdict

def main():
    n, k = map(int, sys.stdin.readline().split())
    teams = []
    for i in range(n):
        s, p, u = map(int, sys.stdin.readline().split())
        teams.append((s, p, u, i))  # (s, p, u, team_id)
    
    s_groups = defaultdict(lambda: {
        'u_queues': defaultdict(list),  # each value is a min-heap of (p, team_id)
        'global_heap': []               # min-heap of (count[u], p, u, team_id)
    })
    
    for s, p, u, team_id in teams:
        group = s_groups[s]
        heapq.heappush(group['u_queues'][u], (p, team_id))
    
    max_s_heap = []  # max-heap implemented using negative values
    
    for s in s_groups:
        group = s_groups[s]
        u_queues = group['u_queues']
        global_heap = group['global_heap']
        for u in u_queues:
            if u_queues[u]:
                p, team_id = u_queues[u][0]
                heapq.heappush(global_heap, (0, p, u, team_id))
        if global_heap:
            heapq.heappush(max_s_heap, (-s, s))
    
    count = defaultdict(int)
    selected = []
    
    for _ in range(k):
        current_s = None
        current_group = None
        
        while max_s_heap:
            neg_s, s = heapq.heappop(max_s_heap)
            group = s_groups.get(s)
            if group and group['global_heap']:
                current_s = s
                current_group = group
                break
        
        if current_s is None:
            break
        
        while True:
            if not current_group['global_heap']:
                break
            cnt_u, p, u, team_id = heapq.heappop(current_group['global_heap'])
            if cnt_u != count[u]:
                continue
            u_queue = current_group['u_queues'][u]
            if not u_queue or u_queue[0][0] != p:
                continue
            selected.append(team_id)
            heapq.heappop(u_queue)
            count[u] += 1
            if u_queue:
                new_p, new_team_id = u_queue[0]
                heapq.heappush(current_group['global_heap'], (count[u], new_p, u, new_team_id))
            if current_group['global_heap']:
                heapq.heappush(max_s_heap, (-current_s, current_s))
            break
    
    for team_id in selected:
        print(team_id)

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