結果

問題 No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:30:32
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,774 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 82,036 KB
実行使用メモリ 105,968 KB
最終ジャッジ日時 2025-04-15 23:32:07
合計ジャッジ時間 10,979 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 47
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
from collections import defaultdict

def main():
    n, k = map(int, sys.stdin.readline().split())
    s_groups = [[] for _ in range(11)]  # S ranges from 0 to 10

    for idx in range(n):
        s, p, u = map(int, sys.stdin.readline().split())
        s_groups[s].append((p, u, idx))

    # Sort each s_group by penalty in ascending order
    for s in range(11):
        s_groups[s].sort()

    u_counts = defaultdict(int)
    current_s = 10  # Start from the highest possible S
    result = []

    for _ in range(k):
        # Find the current highest S with remaining teams
        while current_s >= 0 and not s_groups[current_s]:
            current_s -= 1
        if current_s < 0:
            break  # This should not happen as K <= N

        best_p = float('inf')
        best_u = -1
        best_idx = -1
        best_i = -1

        # Iterate through all teams in current_s group to find the best candidate
        for i, (p, u, idx) in enumerate(s_groups[current_s]):
            current_uc = u_counts[u]
            # Compare based on university count and then penalty
            if (current_uc < u_counts.get(best_u, float('inf'))) or \
               (current_uc == u_counts.get(best_u, float('inf')) and p < best_p):
                best_p = p
                best_u = u
                best_idx = idx
                best_i = i

        # Select the best team found
        result.append(best_idx)
        u_counts[best_u] += 1

        # Remove the selected team from the s_group
        del s_groups[current_s][best_i]

        # Check if current_s group is now empty, move to next S if necessary
        if not s_groups[current_s]:
            current_s -= 1

    for num in result:
        print(num)

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