結果
問題 | No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい |
ユーザー | Kmcode1 |
提出日時 | 2016-10-14 22:48:00 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 252 ms / 4,000 ms |
コード長 | 1,313 bytes |
コンパイル時間 | 4,112 ms |
コンパイル使用メモリ | 186,004 KB |
実行使用メモリ | 36,356 KB |
最終ジャッジ日時 | 2023-08-14 11:33:03 |
合計ジャッジ時間 | 8,147 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 158 ms
14,540 KB |
testcase_01 | AC | 142 ms
15,288 KB |
testcase_02 | AC | 105 ms
13,532 KB |
testcase_03 | AC | 105 ms
10,880 KB |
testcase_04 | AC | 102 ms
10,420 KB |
testcase_05 | AC | 117 ms
13,724 KB |
testcase_06 | AC | 252 ms
36,356 KB |
testcase_07 | AC | 120 ms
14,900 KB |
testcase_08 | AC | 151 ms
29,464 KB |
testcase_09 | AC | 74 ms
9,972 KB |
testcase_10 | AC | 44 ms
4,928 KB |
testcase_11 | AC | 46 ms
5,052 KB |
testcase_12 | AC | 47 ms
5,160 KB |
testcase_13 | AC | 38 ms
4,948 KB |
testcase_14 | AC | 41 ms
5,204 KB |
testcase_15 | AC | 36 ms
5,092 KB |
testcase_16 | AC | 45 ms
5,452 KB |
testcase_17 | AC | 50 ms
5,080 KB |
testcase_18 | AC | 48 ms
5,044 KB |
testcase_19 | AC | 38 ms
4,836 KB |
testcase_20 | AC | 42 ms
5,364 KB |
testcase_21 | AC | 41 ms
4,980 KB |
testcase_22 | AC | 46 ms
5,068 KB |
testcase_23 | AC | 43 ms
5,068 KB |
testcase_24 | AC | 39 ms
4,956 KB |
testcase_25 | AC | 44 ms
5,140 KB |
testcase_26 | AC | 38 ms
5,008 KB |
testcase_27 | AC | 42 ms
4,892 KB |
testcase_28 | AC | 38 ms
4,928 KB |
testcase_29 | AC | 42 ms
5,212 KB |
testcase_30 | AC | 2 ms
4,380 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 63 ms
5,472 KB |
testcase_33 | AC | 66 ms
5,492 KB |
testcase_34 | AC | 86 ms
15,048 KB |
testcase_35 | AC | 2 ms
4,376 KB |
testcase_36 | AC | 2 ms
4,380 KB |
testcase_37 | AC | 2 ms
4,376 KB |
testcase_38 | AC | 2 ms
4,380 KB |
testcase_39 | AC | 2 ms
4,380 KB |
testcase_40 | AC | 3 ms
4,376 KB |
testcase_41 | AC | 5 ms
4,376 KB |
testcase_42 | AC | 5 ms
4,380 KB |
testcase_43 | AC | 5 ms
4,380 KB |
testcase_44 | AC | 5 ms
4,376 KB |
testcase_45 | AC | 2 ms
4,376 KB |
testcase_46 | AC | 9 ms
4,376 KB |
testcase_47 | AC | 9 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int n, k; map<int, vector<pair<int, int> > > mp; //u,p map<int, vector<int> > IDS; priority_queue<pair<int, pair<int,int> > > q; //selected, penalty university map<int, int> sel; vector<int> ans; map<int, deque<pair<int, int> > > team; //university, pena,id int main(){ cin >> n >> k; for (int i = 0; i < n; i++){ int s, p, u; scanf("%d%d%d", &s, &p, &u); mp[-s].push_back(make_pair(u, p)); IDS[-s].push_back(i); } for (auto it = mp.begin(); it != mp.end(); it++){ vector<pair<int, int> > &v = (*it).second; for (int i = 0; i < v.size(); i++){ team[v[i].first].push_back(make_pair(v[i].second, IDS[(*it).first][i])); } for (auto it = team.begin(); it != team.end(); it++){ sort((*it).second.begin(), (*it).second.end()); q.push(make_pair(-sel[(*it).first], make_pair(-(*it).second[0].first, (*it).first))); } while (k>0 && q.size()){ pair<int, pair<int, int> > b = q.top(); q.pop(); k--; int uni = b.second.second; sel[uni]++; ans.push_back(team[uni].front().second); team[uni].pop_front(); if (team[uni].size()){ q.push(make_pair(-sel[uni], make_pair(-team[uni].front().first, uni)) ); } } team.clear(); } for (int i = 0; i < ans.size(); i++){ printf("%d\n", ans[i]); } return 0; }