Submission #1722206

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

struct gausselim
{
	int rank;
	pair<ll,ll> cyc[31];
	void init()
	{
		for(int i = 0; i < 31; i++)
		{
			cyc[i] = mp(0,0);
		}
		rank = 0;
	}
	void add(ll x)
	{
		int tmp = 0;
		for(int i = 30; i >= 0; i--)
		{
			if(x&(1<<i))
			{
				if(cyc[i].fi==0)
				{
					cyc[i].fi = x;
					cyc[i].se = (1<<i)^tmp;
					rank++;
					break;
				}
			}
			//x = min(x, (x^cyc[i]));
			if((x^cyc[i].fi)<x)
			{
				x^=cyc[i].fi;
				tmp^=cyc[i].se;
			}
		}	
	}
};
gausselim base;
vi vec;
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin>>n;
	int s = 0;
	for(int i = 0; i < n; i++)
	{
		int x; cin>>x;
		vec.pb(x^(x-1));
		s^=x;
	}
	//how many of vec[i] xors to x;
	for(int i = 0; i < n; i++)
	{
		base.add(vec[i]);
	}
	ll tmp = 0;
	int x = 0;
	for(int i = 30; i >= 0; i--)
	{
		if(base.cyc[i].fi==0) continue;
		if((s&(1<<i)) != (x&(1<<i)))
		{
			x^=base.cyc[i].fi;
			tmp^=base.cyc[i].se;
		}
	}
	if(x!=s) cout<<-1<<'\n';
	else cout<<__builtin_popcount(tmp)<<'\n';
}

Submission Info

Judge Result