Submission #1000700

---

Source Code Expand

#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve();
void precalc();
clock_t start;
//int timer = 1;

int testNumber = 1;

bool todo = true;

int main() {
#ifdef AIM
    freopen("/home/alexandero/ClionProjects/ACM/input.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
    cout.sync_with_stdio(0);
    cin.tie(0);
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cerr << testNum << endl;
        //cout << "Case #" << testNum++ << ": ";
        solve();
        ++testNumber;
        //++timer;
    }

#ifdef AIM
    cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

    return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

void precalc() {

}

//#define int li

//const int mod = 1000000007;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    int xxor = 0;
    const int L = 30;
    vector<int> has(L);
    for (int i = 0; i< n; ++i) {
        cin >> a[i];
        xxor ^= a[i];
        int cur = a[i];
        int cnt = 0;
        while (cur % 2 == 0) {
            ++cnt;
            cur /= 2;
        }
        ++has[cnt];
    }

    vector<vector<int>> dp(L + 1, vector<int>(2, (int)1e9));
    dp[L][0] = 0;
    for (int i = L; i > 0; --i) {
        for (int par = 0; par < 2; ++par) {
            if (dp[i][par] > 1e8) {
                continue;
            }
            int state = (par ^ bool(xxor & (1 << (i - 1))));
            if (!state) {
                dp[i - 1][par] = min(dp[i - 1][par], dp[i][par]);
                continue;
            }
            if (!has[i - 1]) {
                continue;
            }
            dp[i - 1][par ^ 1] = min(dp[i - 1][par ^ 1], dp[i][par] + 1);
        }
    }

    int res = min(dp[0][0], dp[0][1]);

    if (res > 1e8) {
        cout << "-1\n";
    }
    else {
        cout << res << "\n";
    }

}

Submission Info

Judge Result