SHARE
TWEET

Untitled

a guest Oct 28th, 2019 167 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long i64;
  5.  
  6. struct Stare {
  7.     i64 sleft;
  8.     i64 pmodif, puntil;
  9.     int id; /// adica acum vreau sa modifi tipul care e pe poztia
  10.                             ///pmodif si am voie sa il duc pana la puntil
  11.     int last;
  12.     bool operator< (const Stare & s) const {
  13.         return sleft < s.sleft;
  14.     }
  15. };
  16.  
  17. vector <Stare> Solve(int nr, vector <i64> & vals, vector <i64> & spans, i64 smax, int & need, vector <pair <i64, i64>> & buffer)
  18. {
  19.     /// pun nr oameni
  20.     vector <Stare> ans;
  21.     priority_queue <Stare> stari;
  22.     i64 sleft = smax - spans[nr - 1];
  23.    
  24.     //cerr << "VALS" << endl;
  25.     //for (auto x : vals) cerr << x << " "; cerr << endl;
  26.  
  27.     if (sleft < 0)
  28.         return vector <Stare> ();
  29.  
  30.     stari.push({ sleft, nr - 1, (i64)vals.size() - 1, nr - 1, -1 });
  31.  
  32.     while (!stari.empty()) {
  33.         auto act = stari.top();
  34.         stari.pop();
  35.         ans.push_back(act), need--;
  36.         buffer.push_back({ nr, smax - act.sleft });
  37.         if (need == 0) break;
  38.  
  39.         //cerr << nr << " " << smax - act.sleft << endl;
  40.  
  41.         /// trebuie sa ma extind
  42.         if (act.pmodif != act.puntil) {
  43.             i64 nsleft = act.sleft - vals[act.pmodif + 1] + vals[act.pmodif];
  44.             if (nsleft >= 0) {
  45.                 stari.push({ nsleft, act.pmodif + 1, act.puntil, act.id, ans.back().last });
  46.             }
  47.         }
  48.  
  49.         if (act.id != 0 && act.pmodif > act.id) {
  50.             i64 nsleft = act.sleft - vals[act.id] + vals[act.id - 1];
  51.             if (nsleft >= 0)
  52.                 stari.push({ nsleft, act.id, act.pmodif - 1, act.id - 1, (int)ans.size() - 1 });
  53.         }
  54.     }
  55.  
  56.     return ans;
  57. }
  58.  
  59.  
  60. vector <int> reconstruct(vector <Stare> & ans, vector <int> real, int k)
  61. {
  62.     vector <int> rez(k);
  63.     /// plec de la ans.back()
  64.     int poz = ans.size() - 1;
  65.  
  66.     for (int i = 0; i < k; ++i)
  67.         rez[i] = real[i];
  68.  
  69.     while (poz != -1) {
  70.         rez[ans[poz].id] = real[ans[poz].pmodif];
  71.         // assert(ans[ans[poz].last].id == ans[poz].id + 1);
  72.         poz = ans[poz].last;
  73.     }
  74.  
  75.     return rez;
  76.  
  77. }
  78.  
  79. void test(int n, i64 k, int m, vector <i64> vals)
  80. {
  81.     vector <pair <i64, int>> for_sort(n);
  82.     for (int i = 0; i < n; i++)
  83.         for_sort[i] = { vals[i], i };
  84.     sort(for_sort.begin(), for_sort.end());
  85.  
  86.     vector <int> real(n);
  87.     for (int i = 0; i < n; i++)
  88.         real[i] = for_sort[i].second;
  89.  
  90.     sort(vals.begin(), vals.end());
  91.     vector <i64> spans = vals;
  92.     for (int i = 1; i < n; i++)
  93.         spans[i] += spans[i - 1];
  94.  
  95.     vector <Stare> ans;
  96.     vector <pair <i64, i64>> buffer;
  97.  
  98.     int ch = 1;
  99.     for (int i = n; i > 0 && m; i--) {
  100.         ans = Solve(i, vals, spans, k, m, buffer);
  101.         if (m == 0) {
  102.             ch = i;
  103.             break;
  104.         }
  105.     }
  106.  
  107.     cout << buffer.size() << '\n';
  108.     for (auto i : buffer)
  109.         cout << i.first << ' ' << i.second << '\n';
  110.     if (buffer.size()) {
  111.         auto x = reconstruct(ans, real, ch);
  112.         for (auto i : x)
  113.             cout << i + 1 << ' ';
  114.         cout << '\n';
  115.     }
  116. }
  117.  
  118.  
  119. int main()
  120. {
  121.     ios_base::sync_with_stdio(0);
  122.     cin.tie(0);
  123.     int t;
  124.     cin >> t;
  125.  
  126.     while (t--) {
  127.         i64 n, k, m;
  128.         cin >> n >> k >> m;
  129.         vector <i64> vals(n);
  130.         for (auto & i : vals)
  131.             cin >> i;
  132.  
  133.         test(n, k, m, vals);
  134.     }
  135. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top