fork download 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. #define saleh                         \
  10.     ios_base::sync_with_stdio(false); \
  11.     cin.tie(nullptr);
  12. #define ll long long
  13.  
  14.  
  15. vector < int > a;
  16.  
  17. int cnt_swaps(int l, int r, int h){
  18.     if(l >= r) return 0;
  19.     int m = (l + r) / 2;
  20.     // left part -> [l, m]
  21.     // right part -> [m + 1, r]
  22.     int min_left = INT_MAX, min_right = INT_MAX;
  23.     for(int i = l; i <= m; i++)
  24.         min_left = min(min_left, a[i]);
  25.     for(int i = m + 1; i <= r; i++)
  26.         min_right = min(min_right, a[i]);
  27.     int swaps = min_left > min_right;
  28.     if(abs(min_left - min_right) > (1 << h)) return -1;
  29.     int left_swaps = cnt_swaps(l, m, h - 1);
  30.     int right_swaps = cnt_swaps(m + 1, r, h - 1);
  31.     if(left_swaps == -1 || right_swaps == -1) return -1;
  32.     return swaps + left_swaps + right_swaps;
  33. }
  34.  
  35. int log2(int n){
  36.     int res = 0;
  37.     while(n > 0)
  38.         n >>= 1, res++;
  39.     return res - 1;
  40. }
  41.  
  42. void Solve(){
  43.     int n;
  44.     cin >> n;
  45.     a = vector < int > (n);
  46.     for(auto& x : a)
  47.         cin >> x;
  48.     cout << cnt_swaps(0, n - 1, log2(n) - 1) << '\n';
  49. }
  50.  
  51. int main(){
  52.     int test_cases = 1;
  53.     cin >> test_cases;
  54.     for(int tc = 1; tc <= test_cases; tc++){
  55.         Solve();
  56.     }
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/ETLBQb
language:
C++ (gcc 8.3)
created:
85 days 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!