# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
135339790 |
Practice:
Akpr |
1556B
- 33
|
C++17 (GCC 7-32)
|
Wrong answer on test 2
|
31 ms
|
1032 KB
|
2021-11-14 08:12:46 |
2021-11-14 08:12:46 |
|
#include<bits/stdc++.h>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define fo(i,n) for(i=0;i<n;i++)
ll i,n;
bool checkperfectsquare(ll n){
if (ceil((double)sqrt(n)) == floor((double)sqrt(n)))return true;
else return false;}
vector<ll> divisorsofanum(ll num){//sqrt n complexity
vector<ll> v;
for(ll i = 2; i < sqrt(num);i++){
if(num%i == 0){v.push_back(i);v.push_back(num/i); }}
if(checkperfectsquare(num) == 1)v.push_back(sqrt(num));
return v;}
void solve(){
ll n;
cin >> n;
ll arr[n];
ll even = 0;
ll odd = 0;
for(i =0 ; i < n;i++){cin >> arr[i];
arr[i] = arr[i]%2;
if(arr[i]%2 == 0)even++;
else odd++;
}
if(abs(even-odd) >1){
cout << -1;
return;
}
vector<pair<ll,ll>> v;
ll arr2[n];
for(i =0 ; i < n;i++){
arr2[i] = arr[i];
}
ll steps1 = 0,steps2 = 0;
for(i = 1 ; i < n ;i++){
if(arr[i] != arr[i-1])continue;
else {
if(i == n-1){steps1= INT_MAX;break;}
ll j;
for(j = i ;j < n;j++){
if(arr[j] != arr[i])break;
}
ll k = j;
for(j = k ;j >= i + 1;j--){
swap(arr[j],arr[j-1]);
steps1++;
}
}
}
for(i =0 ; i < n;i++){arr[i] = arr2[i];}
for(i = n - 1 ; i >= 1;i--){
if(arr[i] != arr[i-1]){continue;}
else {
if(i == 1){steps2 = INT_MAX;break;}
ll j;
for(j = i - 1 ;j > -1;j--){
if(arr[j] != arr[i])break;
}
ll k = j;
for(j = k + 1 ;j < i ;j++){
swap(arr[j],arr[j-1]);
steps2++;
}
}
}
cout << min(steps2,steps1);
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t=1;
cin>>t;
while(t--){
solve();
cout << endl;
}
}
Click to see test details