Submission #3516622


Source Code Expand

Copy
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
void init(int n);
int find(int n);
void unite(int x,int y);
bool same(int x, int y);
ll bpow(ll,ll,ll);
typedef vector<int> vec;
typedef vector<vec> mat;
mat mul(mat &A,mat &B);
mat pow(mat A,ll n);
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
const int MOD = 1000000007;

int main()
{
  unsigned int N,a[100001],xo=0,cnt=0;
  cin >> N;
  REP(i,N){
    cin >> a[i];
  }
  REP(i,N){
    xo ^= a[i];
  }
  set<int> sets;
  REP(i,N){
    int las=0;
    while((a[i] &(1 << (las)))==0){
      las++;
    }
    sets.insert(las);
  }
  REP(i,31){
    if((xo >> (30-i)) & 1){
      if(sets.count(30-i)){
        xo = xo ^ ((1 << (31 - i))-1);
        cnt++;
      }else{
        cout << -1 << endl;
        return 0;
      }
    }
  }
  cout << cnt << endl;
  return 0;
}

int par[MAX_N];
int ranks[MAX_N];

//n要素で初期化
void init(int n){
  REP(i,n){
    par[i] = i;
    ranks[i] = 0;
  }

}

//木の根を求める
int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return ;
  if(ranks[x] < ranks[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(ranks[x] == ranks[y]) ranks[x]++;
  }
}

bool same(int x, int y){
  return find(x) == find(y);
}

ll bpow(ll a, ll n,ll mod){
  int i = 0;
  ll res=1;
  while(n){
    if(n & 1)
      res = (res*a) % mod;
    a = (a*a) % mod;
    n >>= 1;
  }
  return res;
}
mat mul(mat &A, mat &B){
  mat C(A.size(),vec(B[0].size()));
    REP(i,A.size())REP(k,B.size())REP(j,B[0].size()){
    C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
  }
  return C;
}

mat pow(mat A,ll n)
{
  mat B(A.size(),vec(A.size()));
  REP(i,A.size()){
    B[i][i] = 1;
  }
  while(n > 0){
    if ( n & 1) B = mul(B,A);
    A = mul(A,A);
    n >>= 1;
  }
  return B;
}

Submission Info

Submission Time
Task C - Cheating Nim
User makss
Language C++14 (GCC 5.4.1)
Score 500
Code Size 2151 Byte
Status
Exec Time 47 ms
Memory 768 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt
All 500 / 500 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, example0.txt, example1.txt
Case Name Status Exec Time Memory
000.txt 1 ms 256 KB
001.txt 1 ms 256 KB
002.txt 43 ms 640 KB
003.txt 14 ms 512 KB
004.txt 16 ms 384 KB
005.txt 13 ms 384 KB
006.txt 42 ms 640 KB
007.txt 47 ms 640 KB
008.txt 42 ms 640 KB
009.txt 42 ms 640 KB
010.txt 42 ms 640 KB
011.txt 43 ms 768 KB
012.txt 42 ms 640 KB
013.txt 42 ms 640 KB
014.txt 42 ms 640 KB
015.txt 42 ms 640 KB
016.txt 42 ms 640 KB
017.txt 42 ms 640 KB
018.txt 42 ms 640 KB
019.txt 43 ms 640 KB
020.txt 42 ms 640 KB
021.txt 5 ms 256 KB
022.txt 5 ms 256 KB
023.txt 41 ms 640 KB
example0.txt 1 ms 256 KB
example1.txt 1 ms 256 KB