fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. int main()
  7. {
  8.     ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  9.  
  10.     int t; cin >> t;
  11.     while(t--) {
  12.         int n, k; cin >> n >> k;
  13.         vector<ll> arr(n);
  14.         for(int i = 0; i < n; i++) {
  15.             cin >> arr[i];
  16.             arr[i] %= k;
  17.             if(arr[i] != 0)
  18.                 arr[i] = k - arr[i];
  19.         }
  20.  
  21.         multiset<ll> myset;
  22.         for(int i = 0; i < n; i++) {
  23.             if(arr[i] == 0)
  24.                 continue;
  25.             myset.insert(arr[i]);
  26.         }
  27.  
  28.         ll x = 0;
  29.         ll ans = 0;
  30.         while(!myset.empty()) {
  31.             auto itm = myset.begin();
  32.             ll itmVal = *itm;
  33.             while(itmVal < x)
  34.                 itmVal += k;
  35.             ll needed = itmVal-x;
  36.             ans += needed+1;
  37.             x += needed+1;
  38.             myset.erase(itm);
  39.             auto tmp = myset.find(x);
  40.             while(tmp != myset.end()) {
  41.                 x ++;
  42.                 ans ++;
  43.                 myset.erase(tmp);
  44.                 tmp = myset.find(x);
  45.             }
  46.         }
  47.         cout << ans << "\n";
  48.     }
  49.  
  50.     return 0;
  51. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
5
4 3
1 2 1 3
10 6
8 7 1 8 3 7 5 10 8 9
5 10
20 100 50 20 100500
10 25
24 24 24 24 24 24 24 24 24 24
8 8
1 2 3 4 5 6 7 8
stdout
copy 
6
24
0
227
8
https://ideone.com/oNqhoj
language:
C++14 (gcc 8.3)
created:
3 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!