Submission #1014165

---

Source Code Expand

//値Aiを1減らしたとき, 全体のxorは「下位log2(Ai & (-Ai))ビット」反転する。
//各xについて, log2(Ai & (-Ai)) = xを満たすiの個数をcnt[x]に入れておく。
//すると以下の問題になる。
//・yの初期値が与えられる。
//・yの下位xビットを反転する操作を高々cnt[x]回できる
//・y=0にできるか？できるなら操作回数を最小化せよ。
//これはxが大きい順に処理すれば解ける。O(N)
//ちなみに, 同じ操作を2回するのは無駄なので, cnt[x]をcnt[x] % 2に置き換えても問題ない。

#include <iostream>
using namespace std;

int n;
int a[100000];
int cnt[100000];

int log2(int x) {
	int i;
	for (i = 0; (1 << i) < x; i++);
	return i;
}

int main() {
	int i;
	
	cin >> n;
	for (i = 0; i < n; i++) cin >> a[i];
	for (i = 0; i < n; i++) cnt[log2(a[i] & -a[i])]++;
	
	int x = 0;
	for (i = 0; i < n; i++) x ^= a[i];
	
	int ans = 0;
	for (i = 29; i >= 0; i--) {
		if ((x >> i) % 2 == 0) continue;
		if (cnt[i] == 0) { cout << -1 << endl; return 0; }
		ans++;
		
		//xの下位iビットを全て反転
		x = x ^ ((1 << i) - 1);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result