結果
問題 | No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい |
ユーザー |
|
提出日時 | 2016-10-14 23:50:03 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,073 ms / 4,000 ms |
コード長 | 2,137 bytes |
コンパイル時間 | 4,098 ms |
コンパイル使用メモリ | 80,496 KB |
実行使用メモリ | 79,908 KB |
最終ジャッジ日時 | 2024-11-22 07:15:09 |
合計ジャッジ時間 | 61,083 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
import java.io.PrintStream; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; public class Y433 { Y433() throws Exception { Scanner in = new Scanner(System.in); PrintStream out = new PrintStream(System.out); int n = in.nextInt(); int k = in.nextInt(); School[] school = new School[100001]; for (int i = 0; i < 100001; i++) { school[i] = new School(); } for (int i = 0; i < n; i++) { int s = in.nextInt(); int p = in.nextInt(); int u = in.nextInt(); school[u].add(new Team(s, p, i)); } PriorityQueue<School> pq = new PriorityQueue<>(); for (int i = 0; i < 100001; i++) { if (school[i].teams.size() > 0) { school[i].sort(); pq.add(school[i]); } } for (int i = 0; i < k; i++) { School sch = pq.poll(); Team team = sch.getLast(); out.println(sch.getLast().name); sch.pop(); if (sch.teams.size() > 0) { pq.add(sch); } } } class Team implements Comparable { int s, p, name; Team(int s, int p, int name) { this.s = s; this.p = p; this.name = name; } @Override public int compareTo(Object o) { Team that = (Team) o; if (s != that.s) return Integer.compare(s, that.s); return Integer.compare(that.p, p); } } class School implements Comparable { int passed; List<Team> teams; School() { passed = 0; teams = new ArrayList(); } void add(Team t) { teams.add(t); } Team pop() { Team team = getLast(); teams.remove(teams.size() - 1); passed++; return team; } void sort() { teams.sort(null); } Team getLast() { return teams.get(teams.size() - 1); } @Override public int compareTo(Object o) { School that = (School) o; if (getLast().s != that.getLast().s) return Integer.compare(that.getLast().s, getLast().s); if (passed != that.passed) return Integer.compare(passed, that.passed); return Integer.compare(getLast().p, that.getLast().p); } } public static void main(String argv[]) throws Exception { new Y433(); } }