結果

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

ソースコード

diff #
raw source code 

import heapq

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    n = int(input[idx])
    idx += 1
    k = int(input[idx])
    idx += 1
    
    teams = []
    for team_idx in range(n):
        s = int(input[idx])
        idx +=1
        p = int(input[idx])
        idx +=1
        u = int(input[idx])
        idx +=1
        teams.append( (s, p, u, team_idx) )
    
    max_s_possible = 10
    s_buckets = []
    for s in range(max_s_possible + 1):
        s_buckets.append({
            'u_data': dict(),  # key: u, value: heap of (p, team_idx)
            'heap': []
        })
    
    for s, p, u, team_idx in teams:
        bucket = s_buckets[s]
        if u not in bucket['u_data']:
            bucket['u_data'][u] = []
        heapq.heappush(bucket['u_data'][u], (p, team_idx))
    
    count = dict()  # Default to 0 if not present
    
    for s in range(max_s_possible, -1, -1):
        bucket = s_buckets[s]
        bucket_heap = bucket['heap']
        for u in bucket['u_data']:
            if not bucket['u_data'][u]:
                continue
            cnt = count.get(u, 0)
            p_min = bucket['u_data'][u][0][0]
            heapq.heappush(bucket_heap, (cnt, p_min, u))
    
    current_max_s = max_s_possible
    while current_max_s >= 0 and not s_buckets[current_max_s]['heap']:
        current_max_s -= 1
    
    result = []
    for _ in range(k):
        while current_max_s >= 0 and not s_buckets[current_max_s]['heap']:
            current_max_s -= 1
        
        if current_max_s < 0:
            break
        
        bucket = s_buckets[current_max_s]
        current_bucket_heap = bucket['heap']
        selected = None
        
        while current_bucket_heap:
            current_count, current_p, current_u = heapq.heappop(current_bucket_heap)
            actual_count = count.get(current_u, 0)
            
            if actual_count != current_count:
                continue
            
            if current_u not in bucket['u_data'] or not bucket['u_data'][current_u]:
                continue
            
            p_min, team_idx = heapq.heappop(bucket['u_data'][current_u])
            selected = team_idx
            
            count[current_u] = actual_count + 1
            
            if bucket['u_data'][current_u]:
                new_p, new_idx = bucket['u_data'][current_u][0]
                new_count = actual_count + 1
                heapq.heappush(current_bucket_heap, (new_count, new_p, current_u))
            
            break
        
        if selected is not None:
            result.append(selected)
    
    for idx in result:
        print(idx)

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