Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.61 KB | None | 0 0
  1. //
  2. // Created by heisenberg on 4/4/20.
  3. //
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. #define fi                                      freopen("in.txt", "r", stdin)
  8. #define fo                                      freopen("out.txt", "w", stdout)
  9.  
  10. #define PII pair<int,int>
  11.  
  12. using namespace std;
  13.  
  14. bool overlaps(PII a, PII b) {
  15.     // 1     5
  16.     //    3     6
  17.     if (a.first < b.first && b.first < a.second) {
  18.         return true;
  19.     }
  20.     //    3   6
  21.     //  1   4
  22.     if (a.first < b.second && b.second < a.second) {
  23.         return true;
  24.     }
  25.  
  26.     if (b.first < a.first && a.first < b.second) {
  27.         return true;
  28.     }
  29.  
  30.     if (b.first < a.second && a.second < b.second) {
  31.         return true;
  32.     }
  33.     return false;
  34. }
  35.  
  36. bool overlapExists(const vector<PII > &name, PII x) {
  37. //    for (int i = name.size() - 1; i >= 0; i--) {
  38.     for (int i = 0; i < name.size(); i++) {
  39.         if (overlaps(name[i], x)) {
  40.             return true;
  41.         }
  42.     }
  43.     return false;
  44. }
  45.  
  46. int main() {
  47. //    fi;
  48.     ios_base::sync_with_stdio(false);
  49.     cin.tie(NULL);
  50.     int t = 0, T, N;
  51.  
  52.     cin >> T;
  53.  
  54.  
  55.     while (T--) {
  56.         vector<PII > v;
  57.  
  58.         t++;
  59.         cout << "Case #" << t << ": ";
  60.         int a, b;
  61.         cin >> N;
  62.         for (int i = 0; i < N; i++) {
  63.             cin >> a >> b;
  64.             v.emplace_back(a, b);
  65.         }
  66.         sort(v.begin(), v.end());
  67.  
  68.  
  69.         vector<PII > cameron;
  70.         vector<PII > james;
  71.         string ans;
  72.  
  73.         cameron.push_back(v[0]);
  74.         ans = ans + 'C';
  75. //        cout << v.size() << endl;
  76.         for (int i = 1; i < v.size(); i++) {
  77.             PII x = v[i];
  78.  
  79.             if (overlapExists(cameron, x)) {
  80.                 if (overlapExists(james, x)) {
  81.                     ans = "IMPOSSIBLE";
  82.                     break;
  83.                 } else {
  84.                     james.emplace_back(x);
  85.                     ans = ans + 'J';
  86.                 }
  87.             } else {
  88.                 cameron.emplace_back(x);
  89.                 ans = ans + 'C';
  90.             }
  91.  
  92. //            if (overlapExists(cameron, x) && overlapExists(james, x)) {
  93. //                ans = "IMPOSSIBLE";
  94. //                break;
  95. //            } else if (overlapExists(cameron, x)) {
  96. //                james.emplace_back(x);
  97. //                ans = ans + 'J';
  98. //            } else if (overlapExists(james, x)) {
  99. //                cameron.emplace_back(x);
  100. //                ans = ans + 'C';
  101. //            } else {
  102. //                cameron.emplace_back(x);
  103. //                ans = ans + 'C';
  104. //            }
  105.         }
  106.         cout << ans << endl;
  107.  
  108.     }
  109.  
  110.     return 0;
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement