fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long
  5. typedef pair<ll,ll> ii;
  6. ll n,m,a[300000],b[300000],lua[300000],res,trace[300000];
  7. queue<ll> A[300000];
  8. vector<ll> kq;
  9. ii D[300000];
  10. int main()
  11. {
  12.     cin >> n >> m;
  13.     for(int i = 1;i<=n;i++){
  14.         cin >> a[i];
  15.         b[i] = a[i] % m;
  16.         ++lua[b[i]];
  17.         A[b[i]].push(a[i]);
  18.         D[i] = ii(a[i],i);
  19.     }
  20.     res = 0;
  21.     ll cur = n/m;
  22.     if(lua[m-1] > cur){
  23.         ll sl = lua[m-1] -cur;
  24.         lua[m-1] = cur;
  25.         trace[m-1] = sl;
  26.         lua[0]+=sl;
  27.         res+=sl;
  28.     }
  29.     for(int i = 0;i<m-1;i++){
  30.         if(lua[i] > cur && lua[i+1] <= cur){
  31.             res+= lua[i] - cur;
  32.             trace[i] = lua[i] - cur;
  33.             lua[i+1] += lua[i] - cur;
  34.             lua[i] = cur;
  35.         }
  36.     }
  37.     if(trace[m-1] != 0){
  38.         for(int i = 1;i<=trace[m-1];i++){
  39.             ll top = A[m-1].front();
  40.             A[m-1].pop();
  41.             A[0].push(top+1);
  42.         }
  43.     }
  44.     for(int i = 0;i<m-1;i++){
  45.         if(trace[i] != 0){
  46.             for(int j = 1;j<=trace[i];j++){
  47.                 ll top = A[i].front();
  48.                 A[i].pop();
  49.                 A[i+1].push(top+1);
  50.             }
  51.         }
  52.     }
  53.     cout << res << "\n";
  54.     for(int i = 0;i<=m-1;i++){
  55.         while(A[i].size() > 0){
  56.             kq.push_back(A[i].front());
  57.             A[i].pop();
  58.         }
  59.     }
  60.     sort(kq.begin(),kq.end());
  61.     sort(D+1,D+n+1);
  62.     for(int i = 1;i<=n;i++)
  63.         trace[D[i].second] = kq[i-1];
  64.     for(int i = 1;i<=n;i++) cout << trace[i] << " ";
  65.     return 0;
  66. }
Runtime error #stdin #stdout 0.12s 204424KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Z6Y8I5
language:
C++14 (gcc 8.3)
created:
5 years 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!