結果
問題 |
No.433 ICPC国内予選の選抜ルールがこんな感じだったらうれしい
|
ユーザー |
![]() |
提出日時 | 2024-12-21 23:39:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 132 ms / 4,000 ms |
コード長 | 1,049 bytes |
コンパイル時間 | 1,944 ms |
コンパイル使用メモリ | 181,232 KB |
実行使用メモリ | 10,932 KB |
最終ジャッジ日時 | 2024-12-21 23:39:41 |
合計ジャッジ時間 | 8,706 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <bits/stdc++.h> #define endl '\n' #define ll long long using namespace std; const int N = 1e5 + 10; int n, k; struct node{ int id, s, p, u; }a[N]; vector < pair < pair <int, int>, int > > U[N]; priority_queue < pair < pair <int, int>, pair <int, int> > > pq; int cnt[N]; int main() { //freopen("icpc.in","r",stdin); //freopen("icpc.out","w",stdout); cin >> n >> k; for (int i = 0; i < n; i ++) { a[i].id = i; cin >> a[i].s >> a[i].p >> a[i].u; U[a[i].u].push_back({{a[i].s, -a[i].p}, i}); } for (int i = 1; i < N; i ++) { if (!U[i].empty()) { sort(U[i].begin(), U[i].end()); int x = U[i].back().second; U[i].pop_back(); pq.push({{a[x].s, 0}, {-a[x].p, x}}); } } while (k --) { pair < pair <int, int>, pair <int, int> > t = pq.top(); pq.pop(); int x = t.second.second; cout << x << '\n'; if (!U[a[x].u].empty()) { cnt[a[x].u] ++; int y = U[a[x].u].back().second; U[a[x].u].pop_back(); pq.push({{a[y].s, -cnt[a[y].u]}, {-a[y].p, y}}); } } return 0; } //Fuck you, Japan.