SHARE
TWEET

Untitled

a guest Nov 13th, 2019 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <set>
  6. #include <map>
  7. #include <iomanip>
  8. #include <string>
  9.  
  10. #define ll long long
  11. #define pii pair<int,int>
  12.  
  13. using namespace std;
  14.  
  15. struct Tuple {
  16.     int val;
  17.     pii i, j;
  18.     Tuple() {
  19.         val = 0;
  20.         i = j = { 0,0 };
  21.     }
  22.     Tuple(int _val, pii _i, pii _j) {
  23.         val = _val;
  24.         i = _i;
  25.         j = _j;
  26.     }
  27. };
  28.  
  29. bool operator < (Tuple &a, Tuple &b) {
  30.     return a.val < b.val;
  31. }
  32.  
  33. int main()
  34. {
  35.     int n, k;
  36.     cin >> n >> k;
  37.     vector<Tuple> pairs;
  38.     vector<vector<int>> field(n, vector<int>(2));
  39.     vector<vector<bool>> used(n, vector<bool>(2));
  40.     vector<vector<int>> ans(n, vector<int>(2));
  41.     for (int i = 0; i < n; i++)
  42.     {
  43.         int a, b;
  44.         cin >> a >> b;
  45.         field[i][0] = a;
  46.         field[i][1] = b;
  47.  
  48.         pairs.push_back(Tuple(a + b, { i, 0 }, { i, 1 }));
  49.         if (i > 0) {
  50.             pairs.push_back(Tuple(field[i - 1][0] + field[i][0], { i - 1, 0 }, { i, 0 }));
  51.             pairs.push_back(Tuple(field[i - 1][1] + field[i][1], { i - 1, 1 }, { i, 1 }));
  52.         }
  53.     }
  54.  
  55.     sort(pairs.begin(), pairs.end());
  56.  
  57.     for (int i = 0; i < k; i++)
  58.     {
  59.         if (pairs.empty())
  60.             break;
  61.         auto p = pairs.back();
  62.         pairs.pop_back();
  63.         if (used[p.i.first][p.i.second] || used[p.j.first][p.j.second])
  64.         {
  65.             i--;
  66.             continue;
  67.         }
  68.  
  69.         used[p.i.first][p.i.second] = used[p.j.first][p.j.second] = true;
  70.         ans[p.i.first][p.i.second] = ans[p.j.first][p.j.second] = i + 1;
  71.     }
  72.  
  73.     for (int i = 0; i < n; i++)
  74.     {
  75.         cout << ans[i][0] << " " << ans[i][1] << "\n";
  76.     }
  77. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top