fork download
copy 
  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
comments (?)
stdin
copy 
2
3 5
2 3 4
4 10
2 9 3 8
stdout
copy 
Case #1: 2
Case #2: 8
https://ideone.com/Wit0Ru
language:
C++14 (clang 8.0)
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!