Facebook
From Tarunkumar Gatla, 1 Month ago, written in C++.
Embed
Download Paste or View Raw
Hits: 122
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define rep(i, a, b) for(int i = (a); i < (b); i++)
  5. #define all(x) (x).begin(), (x).end()
  6. #define vi vector<int>
  7. #define pb push_back
  8. #define ll long long int
  9. #define watch(x) cout<<(#x)<< "is" <<(x) <<endl
  10. #define endl "\n"
  11. #define vii vector<pair<int,int>>
  12. #define f first
  13. #define s second
  14.  
  15. template<typename T>
  16. void output_vector(const vector<T> &v, bool add_one = false, int start = -1, int end = -1) {
  17.     if (start < 0) start = 0;
  18.     if (end < 0) end = int(v.size());
  19.  
  20.     for (int i = start; i < end; i++)
  21.         cout << v[i] + (add_one ? 1 : 0) << (i < end - 1 ? ' ' : '\n');
  22. }
  23.  
  24. bool isPrime(ll n) {
  25.     if(n==2) return true;
  26.     for ( ll i = 2; i * i <= n; ++ i) {
  27.         if (n % i == 0) {
  28.             return false;
  29.         }
  30.     }
  31.     return true;
  32. }
  33.  
  34. // bool prime[ll n];
  35. // void SieveOfEratosthenes(ll n)
  36. // {
  37.    
  38. //     memset(prime, true, sizeof(prime));
  39.  
  40. //     for (ll p = 2; p * p <= n; p++)
  41. //     {
  42. //         if (prime[p] == true)
  43. //         {
  44. //             for (ll i = p * p; i <= n; i += p)
  45. //                 prime[i] = false;
  46. //         }
  47. //     }
  48. // }
  49.  
  50.  
  51.   void solve()
  52.   {
  53.     int n;
  54.     cin>>n;
  55.     vi v(n);
  56.    
  57.     int even = 0;
  58.     int odd = 0;
  59.     rep(i,0,n){
  60.         cin>>v[i];
  61.         if(v[i]&1){
  62.             odd++;
  63.             v[i]=1;
  64.         }
  65.         else{
  66.             even++;
  67.             v[i]=0;
  68.         }
  69.     }
  70.     // rep(i,0,n){
  71.     //     cout<<v[i];
  72.     // }
  73.     if(n%2==0 && (even!=odd)){
  74.         // cout<<even<<" "<<odd<<endl;
  75.         cout<<-1<<endl;
  76.         return;
  77.     }
  78.     if((n&1) and abs(even-odd)!=1){
  79.         cout<<-1<<endl;
  80.         return;
  81.     }
  82.     int ans = 0;
  83.     for(int i = n-2; i>=0; i--){
  84.         if(v[i]!=v[i+1]) continue;
  85.         int j = i-1;
  86.         while(j>=0){
  87.             if(v[j]!=v[i]) break;
  88.             else j--;
  89.         }
  90.         swap(v[i],v[j]);
  91.         ans = ans + i - j;
  92.     }
  93.     cout<<ans<<endl;
  94.    
  95. }
  96. int main()
  97. {
  98.   ios::sync_with_stdio(false);
  99.     cin.tie(0);
  100.     cout.tie(0);
  101.  
  102.  
  103.     int t; cin>>t;
  104.     while(t--){
  105.      solve();
  106.     }
  107. }      
  108.  
  109.