From f7b521a1999c81ce5e1298d0fa9e77c6881fd931 Mon Sep 17 00:00:00 2001 From: Santo Cariotti Date: Sat, 4 Apr 2020 22:26:16 +0200 Subject: Update parenting.cc --- cpp/parenting.cc | 92 +++++++++++++++++++++++--------------------------------- 1 file changed, 37 insertions(+), 55 deletions(-) (limited to 'cpp') 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 +#include #include -#include using namespace std; -short find_free(const vector& c, const vector& 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& a, const pair& b) { - return (a.first + a.second < b.first + b.second && (a.first < a.second || b.first < b.second)); -} - int main() { + using ti = tuple; int T; cin >> T; - vector> p; for(int _ = 0; _ < T; ++_) { int N; cin >> N; - - p.clear(); - string s; - vector _c(24*60+1, true); - vector _j(24*60+1, true); + char* s = new char[N]; + bool check{true}; + ti qq; + priority_queue, greater> 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; -- cgit v1.2.3-18-g5258