From f7b521a1999c81ce5e1298d0fa9e77c6881fd931 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <dcariotti24@gmail.com>
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/parenting.cc')

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;
-- 
cgit v1.2.3-18-g5258