fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define db double
  10.  
  11. const int N = 1e5 + 7;
  12. int n , k;
  13. long long m , a[N];
  14.  
  15. void inp(){
  16.     cin >> n;
  17.     for (int i = 1 ; i <= n ; ++i){
  18.         cin >> a[i];
  19.     }
  20.     cin >> m >> k;
  21.     sort(a + 1 , a + n + 1);
  22. }
  23.  
  24. void sub1(){
  25.     while (m--){
  26.         int i = 1;
  27.         int p = k;
  28.         while (i <= n){
  29.             int j = i;
  30.             while (j < n && a[j + 1] == a[i]) ++j;
  31.             if (j - i + 1 < p){
  32.                 for (int u = i ; u <= j ; ++u) ++a[u];
  33.                 p -= (j - i + 1);
  34.             }
  35.             else{
  36.                 for (int u = j ; u >= j - p + 1 ; --u) ++a[u];
  37.                 break;
  38.             }
  39.             i = j + 1;
  40.         }
  41.     }
  42.     for (int i = 1 ; i <= n ; ++i) cout << a[i] << " ";
  43. }
  44.  
  45. void sub2(){
  46.     long long tol = m * k;
  47.     int i = 1;
  48.     long long cnt = 0;
  49.     while (i <= n){
  50.         ++cnt;
  51.         int j = i;
  52.         while (j < n && a[j + 1] == a[i]){
  53.             ++j;
  54.             ++cnt;
  55.         }
  56.         if (j == n){
  57.             for (int u = 1 ; u <= j ; ++u) a[u] = a[j];
  58.             for (int u = 1 ; u <= j ; ++u) a[u] += tol / cnt;
  59.             for (int u = j ; u >= j - (tol % cnt) + 1 ; --u) ++a[u];
  60.             for (int i = 1 ; i <= n ; ++i) cout << a[i] << " ";
  61.             return;
  62.         }
  63.         if (tol <= (a[j + 1] - a[i]) * cnt){
  64.             for (int u = 1 ; u <= j ; ++u) a[u] = a[j];
  65.             for (int u = 1 ; u <= j ; ++u) a[u] += tol / cnt;
  66.             for (int u = j ; u >= j - (tol % cnt) + 1 ; --u) ++a[u];
  67.             for (int i = 1 ; i <= n ; ++i) cout << a[i] << " ";
  68.             return;
  69.         }
  70.         tol -= (a[j + 1] - a[i]) * cnt;
  71.         i = j + 1;
  72.     }
  73. }
  74.  
  75. long long BIT[N];
  76.  
  77. void update(int x , long long val){
  78.     while (x <= n){
  79.         BIT[x] += val;
  80.         x += x & -x;
  81.     }
  82. }
  83.  
  84. long long get(int x){
  85.     long long res = 0;
  86.     while (x > 0){
  87.         res += BIT[x];
  88.         x -= x & -x;
  89.     }
  90.     return res;
  91. }
  92.  
  93. void sub3(){
  94.     for (int i = 1 ; i <= n ; ++i) update(i , a[i] - a[i - 1]);
  95.     while (m--){
  96.         if (get(k + 1) > get(k)){
  97.             update(1 , 1);
  98.             update(k + 1 , -1);
  99.             continue;
  100.         }
  101.         long long t = get(k);
  102.         int l = 1 , r = k , mid , pos = 0;
  103.         while (l <= r){
  104.             mid = (l + r) >> 1;
  105.             if (get(mid) < t){
  106.                 pos = mid;
  107.                 l = mid + 1;
  108.             }
  109.             else r = mid - 1;
  110.         }
  111.         int p = k;
  112.         if (pos){
  113.             update(1 , 1);
  114.             update(pos + 1 , -1);
  115.             p -= pos;
  116.         }
  117.         l = k + 1 , r = n , mid , pos;
  118.         while (l <= r){
  119.             mid = (l + r) >> 1;
  120.             if (get(mid) == t){
  121.                 pos = mid;
  122.                 l = mid + 1;
  123.             }
  124.             else r = mid - 1;
  125.         }
  126.         update(pos + 1 , -1);
  127.         update(pos - p + 1 , 1);
  128.     }
  129.     for (int i = 1 ; i <= n ; ++i) cout << get(i) << " ";
  130. }
  131.  
  132. void solve(){
  133.     if (n <= 1e3 && m <= 1e3){
  134.         sub1();
  135.         return;
  136.     }
  137.     if (k == 1){
  138.         sub2();
  139.         return;
  140.     }
  141.     if (k == n){
  142.         for (int i = 1 ; i <= n ; ++i) cout << a[i] + m << " ";
  143.         return;
  144.     }
  145.     if (m <= 1e5){
  146.         sub3();
  147.     }
  148. }
  149.  
  150. int main(){
  151. //    freopen("level.inp" , "r" , stdin);
  152. //    freopen("level.out" , "w" , stdout);
  153.     faster;
  154.     inp();
  155.     solve();
  156.     return 0;
  157. }
  158.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CTosSK
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!