結果
問題 |
No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
|
ユーザー |
![]() |
提出日時 | 2023-01-30 20:08:51 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 4,000 ms |
コード長 | 2,384 bytes |
コンパイル時間 | 5,252 ms |
コンパイル使用メモリ | 143,488 KB |
実行使用メモリ | 11,176 KB |
最終ジャッジ日時 | 2024-06-30 05:24:14 |
合計ジャッジ時間 | 8,801 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <climits> #include <map> #include <queue> #include <set> #include <cstring> #include <vector> using namespace std; typedef long long ll; struct Node { int id; int solved_cnt; int penalty; int uid; Node(int id = -1, int solved_cnt = -1, int penalty = -1, int uid = -1) { this->id = id; this->solved_cnt = solved_cnt; this->penalty = penalty; this->uid = uid; } bool operator>(const Node &n) const { if (solved_cnt == n.solved_cnt) { return penalty > n.penalty; } else { return solved_cnt < n.solved_cnt; } } }; struct SubNode { int id; int uid; int selected_cnt; int penalty; SubNode(int id = -1, int uid = -1, int selected_cnt = -1, int penalty = -1) { this->id = id; this->uid = uid; this->selected_cnt = selected_cnt; this->penalty = penalty; } bool operator>(const SubNode &n) const { if (selected_cnt == n.selected_cnt) { return penalty > n.penalty; } else { return selected_cnt > n.selected_cnt; } } }; int main() { int N, K; cin >> N >> K; priority_queue <Node, vector<Node>, greater<Node>> pque_list[100010]; for (int i = 0; i < N; ++i) { int S, P, U; cin >> S >> P >> U; pque_list[U].push(Node(i, S, P, U)); } vector<int> selected_ids; vector<int> selected_counter(100010, 0); for (int s = 10; s >= 0; --s) { priority_queue <SubNode, vector<SubNode>, greater<SubNode>> pque; for (int uid = 1; uid <= 100000; ++uid) { if (pque_list[uid].empty()) continue; if (pque_list[uid].top().solved_cnt < s) continue; Node node = pque_list[uid].top(); pque_list[uid].pop(); pque.push(SubNode(node.id, uid, selected_counter[uid], node.penalty)); } while (not pque.empty() && selected_ids.size() < K) { SubNode s_node = pque.top(); pque.pop(); int uid = s_node.uid; selected_ids.push_back(s_node.id); selected_counter[uid]++; if (pque_list[uid].size() > 0 && pque_list[uid].top().solved_cnt >= s) { Node node = pque_list[uid].top(); pque_list[uid].pop(); pque.push(SubNode(node.id, uid, selected_counter[uid], node.penalty)); } } } for (int id : selected_ids) { cout << id << endl; } return 0; }