SHARE
TWEET

Untitled

a guest Nov 12th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(X) (X).begin(), (X).end()
  6. #define pb push_back
  7. #define rall(X) (X).rbegin(), (X).rend()
  8. #define ll long long
  9. #define ull unsigned long long
  10. #define ld long double
  11. #define fir first
  12. #define sec second
  13.  
  14. int main() {
  15.     ll n,k; cin >> n >> k;
  16.     vector<ll> a(n);
  17.     map<ll, set<ll>> mp;
  18.     ll mx = LLONG_MIN, mn = LLONG_MAX;
  19.  
  20.     for (ll i = 0; i < n; i++) {
  21.         cin >> a[i];
  22.         mp[a[i]].insert(i);
  23.         mx = max(mx, a[i]);
  24.         mn = min(mn, a[i]);
  25.     }
  26.  
  27.     vector<pair<ll, ll>> ans;
  28.  
  29.     while (k > 0 && mx - mn > 1) {
  30.         k--;
  31.         ll pos1 = *mp[mx].begin();
  32.         ll pos2 = *mp[mn].begin();
  33.         mp[mx - 1].insert(pos1);
  34.         mp[mx].erase(pos1);
  35.         mp[mn + 1].insert(pos2);
  36.         mp[mn].erase(pos2);
  37.         ans.pb({pos1 + 1, pos2 + 1});
  38.         while (mp[mx].size() == 0)
  39.             mx--;
  40.         while(mp[mn].size() == 0)
  41.             mn++;
  42.     }
  43.  
  44.     cout << mx - mn << " " << ans.size() << '\n';
  45.  
  46.     for (ll i = 0; i < ans.size(); i++) {
  47.         cout << ans[i].fir << " " << ans[i].sec << '\n';
  48.     }
  49.     return 0;
  50. }
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