#include <bits/stdc++.h> using namespace std; int solve(const vector<pair<pair<int, int>,int>>& r) { //cerr << "solve " ; // for (auto it:r) cerr << "[" << it.first<<","<<it.second<<"] "; //cerr<<endl; priority_queue<int, vector<int>, greater<int>> q; int current_time = 1; int last_time_used = 0; for (const auto& elem : r) { while (current_time < elem.first.first && !q.empty()) { int v = q.top(); q.pop(); if (current_time > v) { // cerr << "dupa" << endl; return -1; } last_time_used = current_time; current_time++; } q.push(elem.first.second); current_time = max(current_time, elem.first.first); } while (!q.empty()) { int v=q.top(); q.pop(); if (current_time > v) return -1; last_time_used = current_time; current_time++; } //cerr << last_time_used << endl; return last_time_used; } int main() { ios_base::sync_with_stdio(false); map<int, vector<pair<pair<int,int>,int>>> RR; int n, ktoignore; cin >> n >> ktoignore; for (int i =0 ; i < n;++i) { int a, b, p; cin >> a >> b >> p; RR[p].emplace_back(make_pair(a, b), i); } vector<vector<pair<pair<int,int>,int>>> R; R.reserve(RR.size()); for (const auto& x : RR) { R.push_back(x.second); sort(R.back().begin(), R.back().end()); } RR.clear(); vector<int> solution(n); int result = 0; while (R.size() > 0) { int last_time_used = 0; for (const auto& r : R) { int temp = solve(r); if (temp == -1) { cout << "NIE" << endl; assert(result == 0); return 0; } last_time_used = max(last_time_used, temp); } for (auto& r : R) { int to_remove = -1; for (int i = 0; i < r.size(); ++i) { if (r[i].first.first <= last_time_used && last_time_used <= r[i].first.second) if (to_remove == -1 or r[to_remove].first.first < r[i].first.first) to_remove = i; } if (to_remove != -1) { solution[r[to_remove].second] = last_time_used; r.erase(r.begin() + to_remove); } for (auto& it : r) { it.first.second = min(it.first.second, last_time_used - 1); assert(it.first.first <= it.first.second); } } for (int i=0; i<R.size(); ++i) { if (R[i].empty()) { swap(R[i], R.back()); R.resize(R.size()-1); --i; } } ++result; } cout << result << endl; for (int x : solution) { assert(x > 0); cout << x << endl; } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 | #include <bits/stdc++.h> using namespace std; int solve(const vector<pair<pair<int, int>,int>>& r) { //cerr << "solve " ; // for (auto it:r) cerr << "[" << it.first<<","<<it.second<<"] "; //cerr<<endl; priority_queue<int, vector<int>, greater<int>> q; int current_time = 1; int last_time_used = 0; for (const auto& elem : r) { while (current_time < elem.first.first && !q.empty()) { int v = q.top(); q.pop(); if (current_time > v) { // cerr << "dupa" << endl; return -1; } last_time_used = current_time; current_time++; } q.push(elem.first.second); current_time = max(current_time, elem.first.first); } while (!q.empty()) { int v=q.top(); q.pop(); if (current_time > v) return -1; last_time_used = current_time; current_time++; } //cerr << last_time_used << endl; return last_time_used; } int main() { ios_base::sync_with_stdio(false); map<int, vector<pair<pair<int,int>,int>>> RR; int n, ktoignore; cin >> n >> ktoignore; for (int i =0 ; i < n;++i) { int a, b, p; cin >> a >> b >> p; RR[p].emplace_back(make_pair(a, b), i); } vector<vector<pair<pair<int,int>,int>>> R; R.reserve(RR.size()); for (const auto& x : RR) { R.push_back(x.second); sort(R.back().begin(), R.back().end()); } RR.clear(); vector<int> solution(n); int result = 0; while (R.size() > 0) { int last_time_used = 0; for (const auto& r : R) { int temp = solve(r); if (temp == -1) { cout << "NIE" << endl; assert(result == 0); return 0; } last_time_used = max(last_time_used, temp); } for (auto& r : R) { int to_remove = -1; for (int i = 0; i < r.size(); ++i) { if (r[i].first.first <= last_time_used && last_time_used <= r[i].first.second) if (to_remove == -1 or r[to_remove].first.first < r[i].first.first) to_remove = i; } if (to_remove != -1) { solution[r[to_remove].second] = last_time_used; r.erase(r.begin() + to_remove); } for (auto& it : r) { it.first.second = min(it.first.second, last_time_used - 1); assert(it.first.first <= it.first.second); } } for (int i=0; i<R.size(); ++i) { if (R[i].empty()) { swap(R[i], R.back()); R.resize(R.size()-1); --i; } } ++result; } cout << result << endl; for (int x : solution) { assert(x > 0); cout << x << endl; } } |