Advertisement
Korotkodul

ТГ D

Sep 29th, 2022 (edited)
1,207
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.93 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. };
  53.  
  54. bool cmp(prt a, prt b) {
  55.     return a.r < b.r;
  56. }
  57.  
  58. struct res{
  59.     ll spent, id, M, rk;//M: M - 1 -- макс кроме нас
  60.     void see() {
  61.         cout << "res\n";
  62.         cout << "spent id M rk\n";
  63.         cout << spent << ' '<< id << ' ' << M << ' ' << rk << "\n\n";
  64.     }
  65. };
  66.  
  67. bool cmp1(res a, res b) {
  68.     return a.spent < b.spent;
  69. }
  70.  
  71. int main() {
  72.     ios::sync_with_stdio(0);
  73.     cin.tie(0);
  74.     cout.tie(0);
  75.     int n; cin >> n;
  76.     vector <prt> a(n);
  77.     for (int i = 0; i < n; ++i) {
  78.         cin >> a[i].r >> a[i].b;
  79.         a[i].id = i;
  80.     }
  81.     sort(a.begin(), a.end(), cmp);
  82.     vector <ll> pf(n);
  83.     pf[0] = a[0].r;
  84.     for (int i = 0; i < n; ++i) {
  85.         pf[i] = pf[i - 1] + a[i].r;
  86.     }
  87.     vector <res> ans;
  88.     for (int i = 0; i < n; ++i) {
  89.         ll L = a[i].r, R = a[n - 1].r, M, ad;
  90.         int lk, rk, mk;
  91.         while (L + 1 < R) {
  92.             M = (L + R) / 2;
  93.             lk = i - 1;
  94.             rk = n - 1;
  95.             while (lk + 1 < rk) {
  96.                 mk = (lk + rk) / 2;
  97.                 if (a[mk].r >= M) {
  98.                     rk = mk;
  99.                 } else {
  100.                     lk = mk;
  101.                 }
  102.             }
  103.             ll del = 0;
  104.             if (rk > 0) {
  105.                 del = pf[rk - 1];
  106.             }
  107.             ad = pf[n - 1] - del - M * (n - rk - 1);
  108.             if (a[i].r + ad >= M) {
  109.                 R = M;
  110.             } else {
  111.                 L = M;
  112.             }
  113.         }
  114.         //НЕТ!!! СРАЗУ ТУТ НАДО ДЕЛАТЬ ПРОВЕРКУ НА ОПТИМАЛЬНОСТЬ
  115.         ll spent = a[i].r + ad - M; //тк нам доостаточно уровня M!!!
  116.         //а зная итоговое rk res, мы смодем восстановить, что каким-то партиям мы вернем срезанные голоса
  117.         res now = {spent, a[i].id, M, rk};
  118.         ans.push_back(now);
  119.     }
  120.     sort(ans.begin(), ans.end(), cmp1);
  121.     cout << "ans\n";
  122.     ans[0].see();
  123. }
  124.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement