問題一覧 > 通常問題

No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 98
作問者 : mayoko_mayoko_ / テスター : 🍡yurahuna🍡yurahuna
2 ProblemId : 684 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-07-14 13:46:47

問題文


ICPC 国内予選に合計 $N$ 個のチームが参加しました。$N$ 個のチームは $0, 1, ..., N-1$ と番号がついています。

各チームについて, 解いた問題の数, ペナルティ, どの大学のチームか, という情報が与えられます。国内予選を突破することのできるチームは $K$ チームです。この $K$ チームを上記の情報に基づいて 1 チームずつ以下のアルゴリズムを用いて決定します。

1. まだ選抜されていないチームのうち, 解いた問題の数がもっとも多いチームを選抜する。
2. まだ選抜されていないチームで最も多くの問題を解いたチームが複数ある場合, 「今までに選抜された同じ大学のチーム数」が少ないチームを選抜する。
3. まだ選抜されていないチームで解いた問題および「今までに選抜された同じ大学のチーム数」が同じチームが複数ある場合, ペナルティが少ないチームを選抜する。

あなたの仕事は, この情報からどのチームが国内予選を突破したのかを求めることです。

入力

$N$ $K$
$S_1$ $P_1$ $U_1$
$S_2$ $P_2$ $U_2$
...
$S_N$ $P_N$ $U_N$


一行目に参加したチーム数 $N$, 選抜されるチーム数$K$ が与えられます。
$1 \leq N \leq 10^5$, $1 \leq K \leq N$
二行目以降の $N$ 行は, 各チームの情報が与えられます。$S_i$ は $i$ 番目のチームの解いた問題の数, $P_i$ は $i$ 番目のチームのペナルティ, $U_i$ は $i$ 番目のチームの出身大学を数値化したものが与えられます。
$0 \leq S_i \leq 10$, $0 \leq P_i \leq 10^6, 1 \leq U_i \leq 10^5$
$P_i, U_i$ は整数
相異なる 2 つの整数 $i, j$ について, $(S_i, P_i)$ と $(S_j, P_j)$ の組が一致していることはない

出力


選抜された $K$ チームを 0-indexed で 1 行ごとに出力してください。ただし, $K$ チームは選抜された順番に出力しなければなりません(詳しいことはサンプルを見てください)。最後に改行してください。

サンプル

サンプル1
入力
5 3
3 100 1
4 200 1
4 300 1
3 150 2
2 50 2
出力
1
2
3


まず 1 チーム目を選択します。
最も多くの問題を解いているのは 1, 2 番目のチームです。どちらも同じ大学出身なので, 「今までに選抜された同じ大学のチーム」は一致しています。ペナルティの小さいのは 1 番目のチームなのでまずは 1 が選抜されます。
次に 2 チーム目を選択します。
まだ選抜されていないチームの中で最も多くの問題を解いているのは 2 番目のチームのみです。なので, 次に 2 番目のチームが選抜されます。
最後に 3 チーム目を選択します。
まだ選抜されていないチームの中で最も多くの問題を解いているのは 0, 3 番目のチームです。大学 1 からはすでに 2 チームが選抜されていますが, 大学 2 からはまだ 1 チームも選抜されていないので, ここでは 3 番目のチームが選抜されます。
よって, 選抜された順に $K$ チームを出力すると 1 2 3 となります。

サンプル2
入力
3 2
4 100 1
5 300 2
3 100 2
出力
1
0


選抜された順に出力しなければならないことに注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。