summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--cpp/parenting.cc92
1 files changed, 37 insertions, 55 deletions
diff --git a/cpp/parenting.cc b/cpp/parenting.cc
index f6117d6..c6a90be 100644
--- a/cpp/parenting.cc
+++ b/cpp/parenting.cc
@@ -1,79 +1,61 @@
// Google Code Jam 2020
#include<iostream>
+#include<queue>
#include<vector>
-#include<algorithm>
using namespace std;
-short find_free(const vector<bool>& c, const vector<bool>& j, int ii, int jj) {
- // 0 = c
- // 1 = j
- bool skip{true};
- for(int i = ii; i < jj; ++i) {
- if(!c.at(i)) {
- skip = false;
- break;
- }
- }
-
- if(skip) return 0;
-
- for(int i = ii; i < jj; ++i) {
- if(!j.at(i)) {
- return -1;
- }
- }
-
- return 1;
-}
-
-bool sortpair(const pair<int, int>& a, const pair<int, int>& b) {
- return (a.first + a.second < b.first + b.second && (a.first < a.second || b.first < b.second));
-}
-
int main() {
+ using ti = tuple<int, int, int>;
int T;
cin >> T;
- vector<pair<int, int>> p;
for(int _ = 0; _ < T; ++_) {
int N;
cin >> N;
-
- p.clear();
- string s;
- vector<bool> _c(24*60+1, true);
- vector<bool> _j(24*60+1, true);
+ char* s = new char[N];
+ bool check{true};
+ ti qq;
+ priority_queue<ti, vector<ti>, greater<ti>> q;
for(int i = 0; i < N; ++i) {
int e1, e2;
cin >> e1 >> e2;
- p.push_back({e1, e2});
+ get<0>(qq) = e1;
+ get<1>(qq) = e2;
+ get<2>(qq) = i;
+ q.push(qq);
}
- for(int i = 0; i < N; ++i) {
- int index1 = p[i].first;
- int index2 = p[i].second;
- int who = find_free(_c, _j, index1, index2);
- switch(who) {
- case 0:
- {
- s += "C";
- for(int j = index1; j < index2; ++j) _c[j] = false;
- break;
- }
- case 1:
- {
- s += "J";
- for(int j = index1; j < index2; ++j) _j[j] = false;
- break;
- }
- }
- if(who == -1) {
- s = "IMPOSSIBLE";
+ int bounds[2] {0, 0};
+
+ while(!q.empty()) {
+ int start = get<0>(q.top());
+ int end = get<1>(q.top());
+ int index = get<2>(q.top());
+
+ if(bounds[0] <= start) {
+ bounds[0] = end;
+ s[index] = 'C';
+ } else if(bounds[1] <= start) {
+ bounds[1] = end;
+ s[index] = 'J';
+ } else {
+ check = false;
break;
}
+ q.pop();
+ }
+
+ cout << "Case #" << _+1 << ": ";
+ if(check) {
+ for(int i = 0; i < N; ++i)
+ cout << s[i];
+ } else {
+ cout << "IMPOSSIBLE";
}
- cout << "Case #" << _+1 << ": " << s << endl;
+
+ cout << endl;
+ delete[] s;
}
return 0;