Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
130640840 Practice:
vaal
1556B - 33 C++17 (GCC 9-64) Wrong answer on test 2 31 ms 12060 KB 2021-10-03 12:57:17 2021-10-03 12:57:17
→ Source
// search files : ctrl + P
// main function starts from around line 320:)
#include "bits/stdc++.h"
// #include "ext/pb_ds/assoc_container.hpp"
// #include "ext/pb_ds/tree_policy.hpp"
// #include "ext/pb_ds/hash_policy.hpp"
// #include "ext/pb_ds/exception.hpp"
// #include "ext/pb_ds/list_update_policy.hpp"
// #include "ext/pb_ds/priority_queue.hpp"
// #include "ext/pb_ds/trie_policy.hpp"
// #include "ext/pb_ds/tag_and_trait.hpp"
#define ld long double
#define ll long long int
#define MOD 1000000007
#define vvn vector<vector<Node*>>
#define vs vector<string>
#define vvs vector<vs>
#define vc vector<char>
#define vvc vector<vc>
#define vb vector<bool>
#define vvb vector<vb>
#define vl vector<ll>
#define vvl vector<vl>
#define vvvl vector<vvl>
#define vd vector<ld>
#define vvd vector<vd>
#define umap unordered_map
#define uset unordered_set
#define chash custom_hash 
#define pq priority_queue
#define pb push_back

#define deb(x) cout << #x << " " << x << endl;
// used for debugging => use like this : deb(x) => output if x == 200 : x 200

#define Fo(i, n) for (ll i=0; i<n; i++)

#define fo(i, a, b) for (ll i=a; i<b; i++)  

// eg on how to use the above macro
// int c = 2, d = 5;
// fo(i, c, d) cout << i << '\n';

// this is only used for ll type. myMax() is used for all types
#define max(...) ({ \
	ll nos[]={ __VA_ARGS__ }; \
	ll n=sizeof(nos)/sizeof(ll); \
    *std::max_element(&nos[0], &nos[n]); \
})
// eg use : best = max(-1, 232, 12, 343, 33);

#define min(...) ({ \
	ll nos[]={ __VA_ARGS__ }; \
	ll n=sizeof(nos)/sizeof(ll); \
    *std::min_element(&nos[0], &nos[n]); \
})

using namespace std;

struct custom_hash {
	// use it like this : umap<ll, ll, chash> mapp;
    static uint64_t splitmix64(uint64_t x) {
        x+=0x9e3779b97f4a7c15;
        x=(x^(x>>30))*0xbf58476d1ce4e5b9;
        x=(x^(x>>27))*0x94d049bb133111eb;
        return x^(x>>31); \
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x+FIXED_RANDOM);
    }
};

template<typename... T>
void read(T&... args) {
    ((cin >> args), ...);
}  // eg : read(x, y, z);

template<typename... T>
void write(T&&... args) {
    ((cout << args << " "), ...);
}  // eg : write(x, y, z, "im a human", 4.5, 6);

template<typename T>
bool f(T x, T y) {
    return x>y;
}  // sort a vector in reverse manner : sort(vec.begin(), vec.end(), f<ll>);

template<typename A, typename B>
ll count(A vec, B ele, bool isSorted) {
    if (isSorted) {
        auto it1=upper_bound(vec.begin(), vec.end(), ele);
        auto it2=lower_bound(vec.begin(), vec.end(), ele);
        return it1-it2;
    }
    return count(vec.begin(), vec.end(), ele);
}

template <typename A> 
A myMax(A a,A b) {
   if (a>b) return a;
   return b;
}

template <typename A, typename ... Args>
A myMax(A a, A b, Args ...args) {
   return myMax(myMax(a,b), args...);
}

template <typename A> 
A myMin(A a,A b) {
   if (a<b) return a;
   return b;
}

template <typename A, typename ... Args>
A myMin(A a, A b, Args ...args) {
   return myMin(myMin(a, b), args...);
}

template<typename A, typename B>
void printMap(map<A, B> mapp) {
    for (auto ele : mapp) cout << ele.first << " : " << ele.second << '\n';
}

template<typename A, typename B>
void printUmap(umap<A, B> mapp) {
    for (auto ele : mapp) cout << ele.first << " : " << ele.second << '\n';
}

string strMap(ll i, ll j) { return to_string(i)+":"+to_string(j); }

ll modExp(ll b, ll p) {
    ll res=1;
    b=b%MOD;
    if (b==0) return 0;
    while (p>0) {
        if (p&1) res=(res*b)%MOD;
        p=p>>1;
        b=(b*b)%MOD;
    }
    return res;
}

ll createPalindrome(ll input, ll b, bool isOdd) {
    ll n=input;
    ll palin=input;
    if (isOdd) n/=b;
    while (n>0) {
        palin=palin*b+(n%b);
        n/=b;
    }
    return palin;
}

void generatePalindromes(ll n) {
    ll number;
 
    // Run two times for odd and even length palindromes
    for (ll j=0; j<2; j++) {
        ll i=1;
        while ((number=createPalindrome(i, 10, j%2)) < n) {
            cout << number << " ";
            i++;
        }
    }
}

ll MAXN=1e6+1;
vl SPF(MAXN);
void spf() { 
    // shortest prime factor
    // o(log n) time 
    SPF[1]=1;
    fo(i, 2, MAXN) SPF[i] = i;
    for (ll i=4; i<MAXN; i+=2) SPF[i] = 2;
    for (ll i=3; i*i<MAXN; i++) {
        if (SPF[i]==i) {
            for (ll j=i*i; j<MAXN; j+=i) if (SPF[j]==j) SPF[j]=i;
        }
    }
}

bool isPowerofTwo(ll n) {
    if (n==0) return 0;
    if ((n&(~(n-1)))==n) return 1;
    return 0;
}

ll modDiv(ll num, ll den) {
    // calculates (num/den)%MOD
    ll inv=(ll)pow(den, MOD-2);
    return ((num%MOD)*(inv%MOD))%MOD;
}

// disjoint set union cluster
void make_set(ll v, vl &parent, vl &size) {
    //o(1). dont forget to declare parent and size array with size (n+1)(not n)
    parent[v]=v;
    size[v]=1;
}
ll find_set(ll v, vl &parent) {
    //o(1)
    if (v==parent[v]) return v;
    return parent[v]=find_set(parent[v], parent);
}
void union_sets(ll a, ll b, vl &parent, vl &size) {
    // o(1)
    a = find_set(a, parent);
    b = find_set(b, parent);
    if (a!=b) {
        if (size[a]<size[b]) swap(a, b);
        parent[b]=a;
        size[a]+=size[b];
    }
}

ll fact(ll n) {
    if (n==0) return 1;
    ll ans=n;
    for (ll i=n-1; i>=1; --i) ans=ans*i;
    return ans;
}

ll nc2(ll n) { return (n*(n-1))/2; }

vl topo(vl jobs, vvl deps) {  // topological sort
    ll n=jobs.size();
	umap<ll, vl, chash> adj;  // adjacency list which maps prerequisites to their parents	
	umap<ll, ll, chash> in;   // it maps a node to the no of prerequisites required for it
	for (int i=0; i<deps.size(); ++i) {
		adj[deps[i][0]].push_back(deps[i][1]);  
		in[deps[i][1]]++;
	}
	deque<ll> q; 
	ll count=0;  // maximum no of jobs that we can complete. if it is less than n, then we cant complete all the jobs
	vl ans;
	for (auto job : jobs)	{
		if (in.find(job)==in.end()) {  // if a job has no prerequisites, then we add it to the queue
			q.push_back(job);
		}
	}
	while (q.size()) {
		count++;  
		int curr=q.front();
		ans.push_back(curr);
		q.pop_front();
		for (auto ele : adj[curr]) {
			in[ele]--;
			if (in[ele]==0) q.push_back(ele);
		}
	}
	if (count<n) return {};
    return ans;
}

ll bin_search(vl vec, ll no) {
    // finds the lower bound of "no" which is stored in "ele". make sure array is sorted!
    ll n=vec.size();
    ll i=0, j=vec.size();
    ll ele, ele2;
    if (vec[0]>=no) return vec[0];
    if (vec.back()<no) return -1;
    while (i<=j) {
        ll mid=(i+j)/2;
        ll el=vec[mid];
        if (mid-1<n && el>=no && vec[mid-1]<no) {
            ele=vec[mid];
            ele2=vec[mid-1];
            break;
        } else if (el<no) i=mid+1;
        else j=mid-1;
    }
    return ele;
}

vl primeFactors(ll n) {
    // o(log n)
    vl ans;
    while (!(n&1)) {        
        ans.pb(2);
        n=n/2;
    }
    for (ll i=3; i<=sqrt(n); i=i+2) {            
        while (n%i==0) {
            ans.pb(i);
            n=n/i;
        }
    }        
    if (n>2) ans.pb(n);
    return ans;
}

ll lcm(ll a, ll b) { return (a*b)/__gcd(a, b); }

// using namespace __gnu_pbds;
// #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
void solve();
//
// debug : deb(x);
// reverse sort a vector vl: sort(vec.begin(), vec.end(), greater<ll>());
// count elements in an array : count(vec, ele, isSorted);
// finding max : myMax(3, 4, 5, 2, 5, ...);
// use strMap(ll i, ll j) to convert pairs to strings
// __builtin_popcount(n);  // counts no of set bits
// priority_queue<ll, vl> // default is max heap

// important functions to study : 
// generating palindromic numbers

// functions:
// modExp(base, power)
// generatePalindrome(n)
// spf()
// isPowerOfTwo(n)
// modDivide(n, k) // modular division
// Note : nlogn soln can pass for 10^9 computations
// next time dont search : __gcd()
// converting char to int : ch-'0'
// lower_bound() can be used in vectors : it returns an iterator to a value not less than ele(logn time)
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout << setprecision(15) << fixed;
    ll t; read(t);
    while (t--) {
        ll n;
        read(n);
        vl vec(n);
        Fo(i, n) read(vec[i]);
        fo(i, 0, n) {
            ll ele=vec[i];
            if (ele&1) {
                vec[i]=1;
            } else {
                vec[i]=2;  
            }
        }
        ll ans=LLONG_MAX;
        vl ones, twos;
        fo(i, 0, n) {
            ll ele=vec[i];
            if (ele==2) {
                twos.pb(i);
            } else ones.pb(i);
        }
        if (abs((ll)ones.size()-(ll)twos.size())>1) {
            cout << -1 << '\n';
            continue;
        }
        ll ans1=0, ans2=0;
        ll one=(ll)ones.size(), two=(ll)twos.size();
        if (one>two || one==two)
        {
            // case 1 : putting ones at even indices                   
            ll i=0;
            ll ind=0;
            while (i<n) {
                ll ele=vec[i];

                // we set the pointer to the wrong location(odd index) of nearest one so that when we find a 
                // two at even index, we swap it with a one at the odd index
                if (ind<ones.size() && (ones[ind]&1)) {}
                else ind++;

                if (ele==2) {
                    if (ind<ones.size())
                        ans1+=abs(ones[ind]-i);
                    ind++;
                    
                } 
                i+=2;
                    
                
            }
            ans=min(ans, ans1);
        }
        if (two>one || one==two)
        {
            // same explanation as above case
            ll i=0, ind=0;
            while (i<n) {
                ll ele=vec[i];
                if ((ind<twos.size() && twos[ind]&1)) { } 
                else ind++;
                if (ele==1) {
                    if (ind<twos.size())
                        ans2+=abs(twos[ind]-i);
                    ind++;
                }
                i+=2;
            }
            // deb(ans2);
            ans=min(ans, ans2);
        }
        cout << ans << '\n';
    }
}

void solve() {
    
}
 
  
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details