Submission #3439336

---

Source Code Expand

/*
#include <boost/functional/hash.hpp>
#include <boost/multiprecision/cpp_int.hpp>
typedef boost::multiprecision::cpp_int mlint;
*/
#include <bits/stdc++.h>
using namespace std;

#define esc(x) cout << (x) << endl,exit(0)
#define print(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define fcout(d) cout << fixed << setprecision(d)
#define each(i,v) for(auto i = begin(v); i != end(v); ++i)
#define reach(i,v) for(auto i = rbegin(v); i != rend(v); ++i)
#define urep(i,s,t) for(int i = (int)(s); i <= (int)(t); ++i)
#define drep(i,s,t) for(int i = (int)(s); i >= (int)(t); --i)
#define rep(i,n) urep(i,0,(n) - 1)
#define rep1(i,n) urep(i,1,(n))
#define rrep(i,n) drep(i,(n) - 1,0)
#define all(v) v.begin(),v.end()
#define rall(v) rbegin(v),rend(v)
#define vct vector
#define prique priority_queue
#define l_bnd lower_bound
#define u_bnd upper_bound
#define rsz resize
#define ers erase
#define emp emplace
#define emf emplace_front
#define emb emplace_back
#define pof pop_front
#define pob pop_back
#define mkp make_pair
#define mkt make_tuple
#define fir first
#define sec second

typedef long long ll;
typedef double db;
typedef vct<vct<ll> > mat;
typedef pair<int,int> pii;
typedef map<int,int> mpii;

template <class T, class U> ostream& operator << (ostream& s, pair<T,U> p) { return s << p.fir << " " << p.sec; }
template <class T> ostream& operator << (ostream& s, vector<T>& v) { for(auto i = v.begin(); i != v.end(); i++) { if(i != begin(v)) s << " "; s << *i; } return s; }

bool odd(ll x) { return x & 1; }
bool even(ll x) { return !odd(x); }
bool parity(ll x, ll y) { return odd(x) ^ even(y); }
ll qceil(ll x, ll y) { return x > 0 ? (x - 1) / y + 1 :  x / y; }
template <class T, class U> bool chmax(T& m, U x) { if(m < x) { m = x; return 1; } return 0; }
template <class T, class U> bool chmin(T& m, U x) { if(m > x) { m = x; return 1; } return 0; }
template <class T> T cmprs(T& v) {
    T tmp = v;
    sort(all(tmp));
    tmp.erase(unique(all(tmp)),end(tmp));
    each(i,v) *i = l_bnd(all(tmp),*i) - begin(tmp) + 1;
    return v;
}

#ifdef Debug
clock_t starting = clock();
void print_time() {
    cout << "--------" << endl;
    cout << "Exec time : " << (double)(clock() - starting) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
}
#endif

void init() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    #ifdef Debug
    atexit(print_time);
    #endif
}

const int dir[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{-1,1},{-1,-1},{1,-1} };
const ll inf32 = (1 << 30) - 1;
const ll inf64 = (1LL << 62) - 1;
const ll mod = 1e9 + 7;
const db eps = 1e-15;

vct<int> a;
vct<bool> b;
vct<pii> p;

int main() {
    init();

    int n,m = 0;
    cin >> n;
    rep(i,n){
        int e;
        cin >> e;
        m ^= e;
        p.emb(e&-e,i);
    }
    sort(all(p));
    int t = 0;
    b.emb(0);
    for(pii k:p){
        while(k.fir > 1 << t){
            t++;
            b.emb(0);
        }
        if(!b.back()) b.back() = 1;
    }
    int dp[40][2];
    rep(j,2)rep(i,40) dp[i][j] = inf32;
    dp[t + 1][0] = 0;
    drep(i,t,0){
        if(1 << i & m){
            dp[i][1] = dp[i + 1][1];
            if(b[i]) chmin(dp[i][1],dp[i + 1][0] + 1);
        }else{
            dp[i][0] = dp[i + 1][0];
            if(b[i]) chmin(dp[i][0],dp[i + 1][1] + 1);
        }
    }
    int ans = min(dp[0][0],dp[0][1]);
    esc(ans < inf32 ? ans : -1);
}

Submission Info

Judge Result