fork download
  1. #include "bits/stdc++.h"
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5.  
  6. #define ll long long
  7.  
  8. const int N = 2e5 + 20;
  9.  
  10. int t, w, n, a[N];
  11.  
  12. typedef tree <
  13. pair <int, int>, null_type,
  14. less<pair <int, int>>, rb_tree_tag, tree_order_statistics_node_update >
  15. ordered_set;
  16. ordered_set s;
  17.  
  18. int main()
  19. {
  20. ios::sync_with_stdio(false);
  21.  
  22. cin >> t;
  23. for(int tc = 1; tc <= t; tc++)
  24. {
  25. cin >> w >> n;
  26. for(int i = 0; i < w; i++) cin >> a[i], a[i]--;
  27. sort(a, a + w);
  28. for(int i = w; i < 2 * w; i++) a[i] = a[i - w] + n;
  29.  
  30. int k = w;
  31. w *= 2;
  32. s.clear();
  33. for(int i = 0; i < k; i++) s.insert({a[i], i});
  34.  
  35. ll old_m = (*s.find_by_order((k + 1) / 2 - 1)).first;
  36. ll d = 0;
  37. for(int i = 0; i < k; i++) d += abs(a[i] - old_m);
  38.  
  39. ll ans = d;
  40. for(int i = k; i < w; i++)
  41. {
  42. s.erase(s.find_by_order(s.order_of_key({a[i - k], i - k})));
  43. s.insert({a[i], i});
  44.  
  45.  
  46. ll m = (*s.find_by_order((k + 1) / 2 - 1)).first;
  47. d = d + abs(m - a[i]) - abs(old_m - a[i - k]);
  48. if(k % 2 == 0) d -= (m - old_m);
  49.  
  50. old_m = m;
  51. ans = min(ans, d);
  52. }
  53.  
  54. cout << "Case #" << tc << ": " << ans << "\n";
  55. }
  56. }
Success #stdin #stdout 0s 4400KB
stdin
2
3 5
2 3 4
4 10
2 9 3 8
stdout
Case #1: 2
Case #2: 8