fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty