Advertisement
Korotkodul

ТГ D как считать spent???

Sep 30th, 2022 (edited)
853
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <queue>
  5. #include <algorithm>
  6. #include <string>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #define pii pair <int, int>
  11. #define pb(x) push_back(x)
  12. using namespace std;
  13. using ll = long long;
  14. using ld = long double;
  15. using db = double;
  16. void cv(vector <int> &v) {
  17.     for (auto x : v) cout << x << ' ';
  18.     cout << "\n";
  19. }
  20.  
  21. void cvl(vector <ll> &v) {
  22.     for (auto x : v) cout << x << ' ';
  23.     cout << "\n";
  24. }
  25.  
  26.  
  27. void cvv(vector <vector <int> > &v) {
  28.     for (auto x : v) cv(x);
  29.     cout << "\n";
  30. }
  31.  
  32. void cvb(vector <bool> v) {
  33.     for (bool x : v) cout << x << ' ';
  34.     cout << "\n";
  35. }
  36.  
  37. void cvs(vector <string>  v) {
  38.     for (auto a : v) {
  39.         cout << a << "\n";
  40.     }
  41. }
  42.  
  43. void cvp(vector <pii> a) {
  44.     for (auto p : a) {
  45.         cout << p.first << ' ' << p.second << "\n";
  46.     }
  47.     cout << "\n";
  48. }
  49.  
  50. struct prt{
  51.     ll r, b, id;
  52.     void see() {
  53.         cout << r << ' ' << b << ' ' << id << "\n\n";
  54.     }
  55. };
  56.  
  57. bool cmp(prt a, prt b) {
  58.     return a.r < b.r;
  59. }
  60.  
  61. struct res{
  62.     ll spent, id, M, rk;//M: M - 1 -- макс кроме нас
  63.     void see() {
  64.         cout << "res\n";
  65.         cout << "spent id M rk\n";
  66.         cout << spent << ' '<< id << ' ' << M << ' ' << rk << "\n\n";
  67.     }
  68. };
  69.  
  70. bool cmp1(res a, res b) {
  71.     return a.spent < b.spent;
  72. }
  73.  
  74.  
  75. bool sh = 1;
  76.  
  77. /*
  78. 6
  79. 1 1
  80. 1 2
  81. 3 3
  82. 3 4
  83. 5 7
  84. 5 8
  85.  
  86. */
  87.  
  88. int main() {
  89.     ios::sync_with_stdio(0);
  90.     cin.tie(0);
  91.     cout.tie(0);
  92.     int n; cin >> n;
  93.     vector <prt> a(n);
  94.     for (int i = 0; i < n; ++i) {
  95.         cin >> a[i].r >> a[i].b;
  96.         a[i].id = i;
  97.     }
  98.     sort(a.begin(), a.end(), cmp);
  99.     vector <ll> pf(n);
  100.     pf[0] = a[0].r;
  101.     for (int i = 1; i < n; ++i) {
  102.         pf[i] = pf[i - 1] + a[i].r;
  103.     }
  104.     vector <res> ans;
  105.  
  106.     if (sh) {
  107.         cout << "a\n";
  108.         for (auto y: a) {
  109.             y.see();
  110.         }
  111.         cout << "pf\n";
  112.         cvl(pf);
  113.     }
  114.  
  115.     for (int i = 0; i < n; ++i) {
  116.         if (a[i].b == -1) {
  117.             continue;
  118.         }
  119.         ll L = a[i].r, R = a[n - 1].r, M, ad;
  120.         if (sh) {
  121.             cout << "L R = " << L << ' ' << R << "\n";
  122.         }
  123.         int lk, rk, mk;
  124.         while (L + 1 < R) {
  125.             M = (L + R) / 2;
  126.             if (sh) {
  127.                 cout << "M = " << M << "\n";
  128.             }
  129.             lk = i - 1;
  130.             rk = n - 1;
  131.             if (sh) {
  132.                 cout << "lk rk = " << lk << ' ' << rk << "\n";
  133.             }
  134.             while (lk + 1 < rk) {
  135.                 mk = (lk + rk) / 2;
  136.                 if (sh) {
  137.                     cout << "mk = " << mk << "\n";
  138.                 }
  139.                 if (a[mk].r >= M) {
  140.                     rk = mk;
  141.                 } else {
  142.                     lk = mk;
  143.                 }
  144.             }
  145.             ll del = 0;
  146.             if (rk > 0) {
  147.                 del = pf[rk - 1];
  148.             }
  149.             if (sh) {
  150.                 cout << "rk del = " << rk << ' ' << del << "\n";
  151.             }
  152.             ad = pf[n - 1] - del - M * (n - rk - 1);
  153.             if (sh) {
  154.                 cout << "ad (cut voices) = " << ad << "\n";
  155.             }
  156.             if (a[i].r + ad >= M) {
  157.                 R = M;
  158.             } else {
  159.                 L = M;
  160.             }
  161.         }
  162.         //НЕТ!!! СРАЗУ ТУТ НАДО ДЕЛАТЬ ПРОВЕРКУ НА ОПТИМАЛЬНОСТЬ
  163.         ll spent = M - a[i].r + a[i].b;  //тк нам доостаточно уровня M!!!
  164.         //а зная итоговое rk res и M, мы смодем восстановить, что каким-то партиям мы вернем срезанные голоса
  165.         res now = {spent, a[i].id, M, rk};
  166.         ans.push_back(now);
  167.  
  168.         if (sh) {
  169.             cout << "i = " << i << "\n";
  170.             cout << "now\n";
  171.             now.see();
  172.         }
  173.     }
  174.     sort(ans.begin(), ans.end(), cmp1);
  175.  
  176.     if (sh) {
  177.         cout << "ans\n";
  178.         for (auto y: ans) {
  179.             y.see();
  180.         }
  181.     }
  182.  
  183.     if (sh) {
  184.         cout << "RES ANS\n";
  185.         ans[0].see();
  186.     }
  187. }
  188.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement