Submission #3887719

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define show(x) cerr << #x << " " << x << endl

typedef long long ll;
typedef unsigned long long ull;

constexpr const int INT_INF=0x3f3f3f3f; // 1061109567
constexpr const ll LL_INF=0x3f3f3f3f3f3f3f3f; // 4557430888798830399

template <typename T> bool chmin(T &a, T b) {
    if (a > b) {a = b;return true;}return false;
}

template <typename T> bool chmax(T &a, T b) {
    if (a < b) {a = b;return true;}return false;
}

// INT
#define GCD(a, b) __gcd(a, b)
template <typename T> T LCM(T a, T b) {return a / GCD(a, b) * b;}
template <typename T> T EXTGCD(T a, T b, T& x, T& y) {
    T d = a;
    if (b != 0) {d=EXTGCD(b,a%b,y,x);y-=(a/b)*x;}
    else x=1,y=0;
    return d;
}
template <typename T> bool is_prime(T a) {
    for(int i=2;i*i<=a;i++)if(a%i==0)return 1;
    return 0;
}

// MOD
const ll MOD = 1000000000 + 7;
#define add(a, b) ((a % MOD) + (b % MOD)) % MOD
#define mul(a, b) ((a % MOD) * (b % MOD)) % MOD
#define sub(a, b) ((a % MOD) + MOD - (b % MOD)) % MOD
template <typename T> T mod_inverse(T a, T mod, bool prime){ // if mod is prime, "prime" is true.
    if(prime){
        T tmp=mod-2,now=a,res=1;while(tmp){if(tmp&1)res=mul(res,now);now=mul(now,now);tmp>>=1;}
        return res;
    }else{T x,y;EXTGCD(a,mod,x,y);return (mod+x%mod)%mod;}
}
#define divide(a, b) ((a % MOD) * (mod_inverse(b, MOD, true))) % MOD

//LLの数値をつかう時は最後にLをつける癖をつけよう
//
//  　　┓　　　┏
//  　＊┗┓　┏┛
//  　　　┫　┣　＊
//  　┏┳┻━┻┳┓
//  　┗┫　　　┣┛
//  ＊　┣　　━┃　＊        Merry Christmas!!
//  　┏┛　　〃┃
//  　┃●　　　┣━┳┓
//  　┗┻┳━━┛　┣┛
//  　＊　┃┏┓┣┓┃
//WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

int n;
ll a[100001];
int in[50];
int num[50];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    FILE *stream1;
    //FILE *stream2;
    stream1 = freopen("/Users/aim_cpo/CLionProjects/competitive/in.txt", "r", stdin);
    //stream2 = freopen("out.txt", "w", stdout);
    if (stream1 == nullptr) return 0;
    //if (stream2 == NULL) return 0;
#endif
    // テキトー考察
    //
    // 各山から最大で1個石を取り除いてa[0] xor a[1] ... xor a[n - 1] = 0 にする(できなければ-1)
    // a[i] から石を1個とると、a[i]を2進数で表したときの一番最初のbitが立っている桁は0になり、それより小さい桁は全部1になる
    // i - 1桁目から0桁目までは1になるので、感覚的には0桁目に近い小さな桁を偶数にするチャンスは沢山あるが、大きな桁を偶数にする
    // チャンスはあまりなさそう?
    // この適当な感覚を信じると、上の桁から見ていって、bitの立っている個数が奇数の桁を偶数にする事ができるかどうかを調べていけばいい
    // 偶数にする方法は1足すのと1引くの2通りがあるが、1足す方法だと今見ている桁より上の桁が全部奇数になってしまう
    // この方法を採用しても結局はbitが最初立っていた場所を引く方法しかないので、1足す方法はだめ
    // というわけで、要はある桁のbitの立っている個数が奇数だったら、そのbitを1から0にできるa[j]が存在するかどうかを考えるだけでいい
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        ll now = a[i];
        int cont = 0;
        while (now) {
            if (now & 1) {
                in[cont]++;
                break;
            }
            cont++;
            now >>= 1;
        }
    }
    for (int i = 0; i < n; i++) {
        ll now = a[i];
        int cont = 0;
        while (now) {
            if (now & 1) {
                num[cont]++;
            }
            cont++;
            now >>= 1;
        }
    }
    int res = 0;
    for (int i = 49; i >= 0; i--) {
        if (num[i] & 1) {
            if (in[i]) {
                res++;
                in[i]--;
                num[i]--;
                for (int j = i - 1; j >= 0; j--) {
                    num[j]++;
                }
            } else {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << res << endl;
#ifdef  LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s.\n";
#endif
    return 0;
}

Submission Info

Judge Result