Guest User

D - Joaozao, The Digit Maker

a guest
Aug 29th, 2017
147
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define mk make_pair
  4. #define fi first
  5. #define se second
  6. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  7. using namespace std;
  8. typedef vector<int> vi;
  9. typedef pair<int,int> ii;
  10. typedef long long ll;
  11. typedef vector<bool> vb;
  12. const int N=200010;
  13.  
  14. int n, v[N], b;
  15.  
  16. int main(void) {
  17.     ios::sync_with_stdio(false);
  18.     cin >> n >> b;
  19.     multiset<int> q;
  20.  
  21.     for (int i = 0; i<2*n; i++) {
  22.         int x;cin>>x;
  23.         q.insert(x);
  24.     }
  25.  
  26.     vi ans;
  27.  
  28.     multiset<int>::reverse_iterator it = q.rbegin();
  29.  
  30.     vector<int> qq;
  31.  
  32.     while (!q.empty()) {
  33.         int x = *q.rbegin();
  34.  
  35.         q.erase(q.find(x));
  36.  
  37.         auto itx = q.upper_bound(b-x-1);
  38.  
  39.         if (itx == q.begin()) {
  40.             qq.pb(x);
  41.         }
  42.         else {
  43.             itx--;
  44.             ans.pb(x + *itx);
  45.             q.erase(itx);
  46.         }
  47.     }
  48.  
  49.     sort(qq.begin(), qq.end());
  50.  
  51.     for (int i = qq.size()-1; i>=0; i-=2) {
  52.         ans.pb(qq[i]+qq[i-1]-b);
  53.     }
  54.     sort(ans.rbegin(), ans.rend());
  55.  
  56.     for (int i = 0; i<ans.size(); i++)
  57.         cout << ans[i] << " ";
  58.     cout << '\n';
  59.    
  60.     return 0;
  61. }
RAW Paste Data