diff options
author | Santo Cariotti <dcariotti24@gmail.com> | 2020-04-04 22:26:16 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2020-04-04 22:26:16 +0200 |
commit | f7b521a1999c81ce5e1298d0fa9e77c6881fd931 (patch) | |
tree | d444272c5a4021b8b686c8601cbf12ae5eeef01b /cpp | |
parent | 5fc340e2416e96221f8e8b757cc9aaadecdf6b71 (diff) |
Diffstat (limited to 'cpp')
-rw-r--r-- | cpp/parenting.cc | 92 |
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; |