Advertisement
he_obviously

Untitled

May 25th, 2020
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.76 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. #define pii pair<int, int>
  10.  
  11. struct person {
  12.  
  13.     int exp;
  14.     int type;
  15.     int pos;
  16.  
  17.     person() {
  18.         this->exp = -1;
  19.         this->type = -1;
  20.         this->pos = -1;
  21.     }
  22.  
  23.     person(int e, int t, int p) {
  24.         this->exp = e;
  25.         this->type = t;
  26.         this->pos = p;
  27.     }
  28. };
  29.  
  30. struct dance {
  31.  
  32.     int dif;
  33.     person first;
  34.     person second;
  35.  
  36.     dance() {
  37.         this->dif = -1;
  38.         this->first = { -1, -1, -1 };
  39.         this->second = { -1, -1, -1 };
  40.     }
  41.  
  42.     dance(int d, person a, person b) {
  43.         this->dif = d;
  44.         this->first = a;
  45.         this->second = b;
  46.     }
  47. };
  48.  
  49. bool operator<(person a, person b) {
  50.     if (a.exp == b.exp) {
  51.         if (a.pos == b.pos) {
  52.             return a.type < b.type;
  53.         }
  54.         return a.pos < b.pos;
  55.     }
  56.     return a.exp < b.exp;
  57. }
  58.  
  59. bool operator!=(person a, person b) {
  60.     return (a.exp != b.exp || a.type != b.type || a.pos != b.pos);
  61. }
  62.  
  63. bool operator==(person a, person b) {
  64.     return (a.exp == b.exp && a.type == b.type && a.pos == b.pos);
  65. }
  66.  
  67. bool operator<(dance a, dance b) {
  68.     if (a.dif == b.dif) {
  69.         if (a.first == b.first) {
  70.             return a.second < b.second;
  71.         }
  72.         return a.first < b.first;
  73.     }
  74.     return a.dif < b.dif;
  75. }
  76.  
  77. int main() {
  78.  
  79.     ios_base::sync_with_stdio(0);
  80.     cin.tie(0); cout.tie(0);
  81.  
  82.     int n;
  83.     cin >> n;
  84.  
  85.     vector <int> boys(n), girls(n);
  86.  
  87.     for (int i = 0; i < n; ++i) {
  88.         cin >> boys[i];
  89.     }
  90.  
  91.     for (int i = 0; i < n; ++i) {
  92.         cin >> girls[i];
  93.     }
  94.  
  95.     set <person> order;
  96.  
  97.     for (int i = 0; i < n; ++i) {
  98.         order.insert({ boys[i], 1, i + 1 });
  99.     }
  100.  
  101.     for (int i = 0; i < n; ++i) {
  102.         order.insert({ girls[i], 2, i + 1 });
  103.     }
  104.  
  105.     set <dance> pairs;
  106.  
  107.     for (auto it = ++order.begin(); it != order.end(); ++it) {
  108.         dance cur;
  109.         cur.dif = (*it).exp - (*(--it)).exp;
  110.         ++it;
  111.         cur.first = *(--it);
  112.         ++it;
  113.         cur.second = *it;
  114.         pairs.insert(cur);
  115.     }
  116.  
  117.     vector <pii> ans;
  118.  
  119.     person last = { 1000000001, -1, -1 };
  120.     order.insert(last);
  121.  
  122.     /*for (person x : order) {
  123.         cout << x.exp << " " << x.type << " " << x.pos << "\n";
  124.     }
  125.  
  126.     for (dance x : pairs) {
  127.         cout << x.dif << " " << x.first.pos << " " << x.second.pos << "\n";
  128.     }*/
  129.  
  130.     while (!pairs.empty()) {
  131.  
  132.         dance cur = *pairs.begin();
  133.  
  134.         //cout << "ok " << cur.dif << " " << cur.first.type << "-" << cur.first.pos << " " << cur.second.type << "-" << cur.second.pos << "\n";
  135.  
  136.         if (cur.first.type != cur.second.type && order.find(cur.first) != order.end() && order.find(cur.second) != order.end()) {
  137.  
  138.             if (cur.first.type == 1) {
  139.                 ans.push_back({ cur.first.pos, cur.second.pos });
  140.             }
  141.             else {
  142.                 ans.push_back({ cur.second.pos, cur.first.pos });
  143.             }
  144.  
  145.             if (order.find(cur.first) != order.begin() && (*(++order.find(cur.second))) != last) {
  146.                 dance now;
  147.                 now.first = (*(--order.find(cur.first)));
  148.                 now.second = (*(++order.find(cur.second)));
  149.                 now.dif = now.second.exp - now.first.exp;
  150.                 //cout << "insert: " << now.dif << " " << now.first.type << "-" << now.first.pos << " " << now.second.type << "-" << now.second.pos << "\n";
  151.                 pairs.insert(now);
  152.             }
  153.  
  154.             order.erase(cur.first);
  155.             order.erase(cur.second);
  156.  
  157.         }
  158.  
  159.         pairs.erase(cur);
  160.     }
  161.  
  162.     for (auto p : ans) {
  163.         cout << p.first << " " << p.second << "\n";
  164.     }
  165.  
  166.     return 0;
  167. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement