結果
問題 |
No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:26:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 610 ms / 4,000 ms |
コード長 | 998 bytes |
コンパイル時間 | 310 ms |
コンパイル使用メモリ | 82,272 KB |
実行使用メモリ | 134,912 KB |
最終ジャッジ日時 | 2025-04-15 23:27:52 |
合計ジャッジ時間 | 17,015 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
import heapq from collections import defaultdict n, k = map(int, input().split()) teams = [] for idx in range(n): s, p, u = map(int, input().split()) teams.append((s, p, u, idx)) teams_by_u = defaultdict(list) for s, p, u, idx in teams: teams_by_u[u].append((s, p, idx)) for u in teams_by_u: teams_by_u[u].sort(key=lambda x: (-x[0], x[1])) current_idx = defaultdict(int) count = defaultdict(int) heap = [] for u in teams_by_u: if teams_by_u[u]: s, p, idx = teams_by_u[u][0] heapq.heappush(heap, (-s, count[u], p, u, idx)) current_idx[u] = 0 selected = [] for _ in range(k): s_neg, cnt_u, p, u, idx = heapq.heappop(heap) selected.append(idx) count[u] += 1 current = current_idx[u] if current + 1 < len(teams_by_u[u]): current_idx[u] += 1 next_s, next_p, next_idx = teams_by_u[u][current_idx[u]] heapq.heappush(heap, (-next_s, count[u], next_p, u, next_idx)) for team_idx in selected: print(team_idx)