Submission #1247855
Source Code Expand
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <random>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
using ti3 = tuple<int, int, int>;
using vti3 = vector<ti3>;
template<class T, int s>using va = vector<array<T, s>>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define rrep(i,a) for(int i=(a)-1;i>=0;i--)
#define rrep1(i,a) for(int i=a;i;i--)
const ll mod = 1000000007;
#define REP rep
template<class T>using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>using pque = priority_queue<T, vector<T>, function<T(T, T)>>;
template <class T>
inline void hash_combine(size_t & seed, const T & v) {
hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std {
template<typename S, typename T> struct hash<pair<S, T>> {
inline size_t operator()(const pair<S, T> & v) const {
size_t seed = 0;
hash_combine(seed, v.first);
hash_combine(seed, v.second);
return seed;
}
};
// Recursive template code derived from Matthieu M.
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl{
static void apply(size_t& seed, Tuple const& tuple){
HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
hash_combine(seed, std::get<Index>(tuple));
}
};
template <class Tuple>
struct HashValueImpl<Tuple, 0>{
static void apply(size_t& seed, Tuple const& tuple){
hash_combine(seed, std::get<0>(tuple));
}
};
template <typename ... TT>
struct hash<std::tuple<TT...>>{
size_t operator()(std::tuple<TT...> const& tt) const{
size_t seed = 0;
HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
return seed;
}
};
}
template<class T>int id(vector<T> &a, T b) {
return lower_bound(ALL(a), b) - a.begin();
}
ll pow(ll base, ll i, ll mod) {
ll a = 1;
while (i) {
if (i & 1) {
a *= base;
a %= mod;
}
base *= base;
base %= mod;
i /= 2;
}
return a;
}
ll gcd(ll a, ll b) {
while (b) {
ll c = a%b;
a = b;
b = c;
}
return a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b)*b;
}
int popcnt(unsigned long long a) {
a = (a & 0x5555555555555555) + (a >> 1 & 0x5555555555555555);
a = (a & 0x3333333333333333) + (a >> 2 & 0x3333333333333333);
a = (a & 0x0f0f0f0f0f0f0f0f) + (a >> 4 & 0x0f0f0f0f0f0f0f0f);
a = (a & 0x00ff00ff00ff00ff) + (a >> 8 & 0x00ff00ff00ff00ff);
a = (a & 0x0000ffff0000ffff) + (a >> 16 & 0x0000ffff0000ffff);
return (a & 0xffffffff) + (a >> 32);
}
class unionfind {
vector<int> par, rank, size_;//速度ではなくメモリ効率を考えるならrankのかわりにsizeを使う
public:
unionfind(int n) :par(n), rank(n), size_(n, 1) {
iota(ALL(par), 0);
}
int find(int x) {
if (par[x] == x)return x;
return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x), y = find(y);
if (x == y)return;
if (rank[x] < rank[y])swap(x, y);
par[y] = x;
size_[x] += size_[y];
if (rank[x] == rank[y])rank[x]++;
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return size_[find(x)];
}
};
template<class T, class Func = function<T(T, T)>>
class segtree {
vector<T> obj;
int offset;
Func updater;
T e;
int bufsize(int num) {
int i = 1;
for (; num >i; i <<= 1);
offset = i - 1;
return (i << 1) - 1;
}
T query(int a, int b, int k, int l, int r) {
if (r <= a || b <= l)return e;
if (a <= l && r <= b)return obj[k];
else return updater(query(a, b, k * 2 + 1, l, (l + r) / 2), query(a, b, k * 2 + 2, (l + r) / 2, r));
}
/*
template<class QF = function<T(T, T)>>
auto query(int a, int b, int k, int l, int r,QF qf) {
if (r <= a || b <= l)return e;
if (a <= l && r <= b)return obj[k];
else return qf(query(a, b, k * 2 + 1, l, (l + r) / 2, qf), query(a, b, k * 2 + 2, (l + r) / 2, r, qf));
}*/
public:
T query(int a, int b) {//[a,b)
return query(a, b, 0, 0, offset + 1);
}/*
template<class QF = function<T(T, T)>>
auto query(int a, int b,QF &&qf) {//[a,b)
return query(a, b, 0, 0, offset + 1,qf);
}*/
void updateall(int l = 0, int r = -1) {
if (r < 0)r = offset + 1;
l += offset, r += offset;
do {
l = l - 1 >> 1, r = r - 1 >> 1;
for (int i = l; i < r; i++)obj[i] = updater(obj[i * 2 + 1], obj[i * 2 + 2]);
} while (l);
}
void update(int k, T &a) {
k += offset;
obj[k] = a;
while (k) {
k = k - 1 >> 1;
obj[k] = updater(obj[k * 2 + 1], obj[k * 2 + 2]);
}
}
segtree(int n, T e, const Func &updater = Func()) :obj(bufsize(n), e), e(e), updater(updater) {}
segtree(vector<T> &vec, T e, const Func &updater = Func()) :obj(bufsize(vec.size()), e), e(e), updater(updater) {
copy(vec.begin(), vec.end(), obj.begin() + offset);
updateall();
}
typename vector<T>::reference operator[](int n) {
return obj[n + offset];
}
};
template<class T = int>
class BIT {//多次元BITはループをネストすればいいらしい。
vector<T> bit;
int n;
public:
BIT(int n) :bit(n + 1, 0) {}
void add(int i, T x) {
i++;
while (i <= n) {
bit[i] += x;
i += i&-i;
}
}
T sum(int i) {
T s = 0;
i++;
while (i) {
s += bit[i];
i &= i - 1;
}
return s;
}
};
template<class T = int>
class rangeadd {
BIT<T> b0, b1;
public:
rangeadd(int n) :b0(n), b1(n) {};
void add(int l, int r, T x) {//[l,r)
b0.add(l, -x*(l - 1));
b1.add(l, x);
b0.add(r, x*r);
b1.add(r, -x);
}
T sum(int i) {
if (i < 0)return 0;
return b0.sum(i) + b1.sum(i)*i;
}
T sum(int l,int r) {
return sum(r - 1) - sum(l - 1);
}
};
typedef complex<ld> P;
typedef vector<P> VP;
const ld eps = 1e-11, pi = acos(-1.0);
ld dot(P a, P b) { return real(conj(a) * b); }
ld cross(P a, P b) { return imag(conj(a) * b); }
namespace std {
bool operator<(const P &a, const P &b) {
return abs(a.real() - b.real()) < eps ? a.imag() < b.imag() : a.real() < b.real();
}
}
struct L { P a, b; };//line->l,segment->s
struct C { P p; ld r; };
int ccw(P a, P b, P c) {
b -= a; c -= a;
if (cross(b, c) > eps) return 1; // counter clockwise
if (cross(b, c) < -eps) return -1; // clockwise
if (dot(b, c) < 0) return 2; // c--a--b on line
if (norm(b) < norm(c)) return -2; // a--b--c on line
return 0; // a--c--b on line
}
bool isis_ll(L l, L m) {//is intersect
return abs(cross(l.b - l.a, m.b - m.a)) > eps;
}
bool isis_ls(L l, L s) {
ld a = cross(l.b - l.a, s.a - l.a);
ld b = cross(l.b - l.a, s.b - l.a);
return (a * b < eps);
}
bool isis_lp(L l, P p) {
return abs(cross(l.b - p, l.a - p)) < eps;
}
bool isis_ss(L s, L t) {
return ccw(s.a, s.b, t.a) * ccw(s.a, s.b, t.b) <= 0 &&
ccw(t.a, t.b, s.a) * ccw(t.a, t.b, s.b) <= 0;
}
P is_ll(L s, L t) { //intersect
P sv = s.b - s.a, tv = t.b - t.a;
return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
bool isis_sp(L s, P p) {
return abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps;
}
P proj(L l, P p) {
ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
return l.a + t * (l.a - l.b);
}
ld dist_lp(L l, P p) {
return abs(p - proj(l, p));
}
ld dist_ll(L l, L m) {
return isis_ll(l, m) ? 0 : dist_lp(l, m.a);
}
ld dist_ls(L l, L s) {
if (isis_ls(l, s)) return 0;
return min(dist_lp(l, s.a), dist_lp(l, s.b));
}
ld dist_sp(L s, P p) {
P r = proj(s, p);
if (isis_sp(s, r)) return abs(r - p);
return min(abs(s.a - p), abs(s.b - p));
}
ld dist_ss(L s, L t) {
if (isis_ss(s, t)) return 0;
ld a = min(dist_sp(s, t.a), dist_sp(t, s.a));
ld b = min(dist_sp(s, t.b), dist_sp(t, s.b));
return min(a, b);
}
VP is_cc(C c1, C c2) {
VP res;
ld d = abs(c1.p - c2.p);
ld rc = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d);
ld dfr = c1.r * c1.r - rc * rc;
if (abs(dfr) < eps) dfr = 0.0;
else if (dfr < 0.0) return res; // no intersection
ld rs = sqrt(dfr);
P diff = (c2.p - c1.p) / d;
res.push_back(c1.p + diff * P(rc, rs));
if (dfr != 0.0) res.push_back(c1.p + diff * P(rc, -rs));
return res;
}
bool isis_vc(vector<C> vc) {
VP crs;
int n = vc.size();
rep(i, n)rep(j, i)
for (P p : is_cc(vc[i], vc[j]))
crs.push_back(p);
rep(i, n)
crs.push_back(vc[i].p);
for (P p : crs) {
bool valid = true;
rep(i, n)
if (abs(p - vc[i].p)>vc[i].r + eps)
valid = false;
if (valid) return true;
}
return false;
}
VP is_lc(C c, L l) {
VP res;
ld d = dist_lp(l, c.p);
if (d < c.r + eps) {
ld len = (d > c.r) ? 0.0 : sqrt(c.r * c.r - d * d); //safety;
P nor = (l.a - l.b) / abs(l.a - l.b);
res.push_back(proj(l, c.p) + len * nor);
res.push_back(proj(l, c.p) - len * nor);
}
return res;
}
VP is_sc(C c, L l) {
VP v = is_lc(c, l), res;
for (P p : v)
if (isis_sp(l, p)) res.push_back(p);
return res;
}
vector<L> tangent_cp(C c, P p) {//円の接線?
vector<L> ret;
P v = c.p - p;
ld d = abs(v);
ld l = sqrt(norm(v) - c.r * c.r);
if (isnan(l)) { return ret; }
P v1 = v * P(l / d, c.r / d);
P v2 = v * P(l / d, -c.r / d);
ret.push_back(L{ p, p + v1 });
if (l < eps) return ret;
ret.push_back(L{ p, p + v2 });
return ret;
}
vector<L> tangent_cc(C c1, C c2) {
vector<L> ret;
if (abs(c1.p - c2.p) - (c1.r + c2.r) > -eps) {
P center = (c1.p * c2.r + c2.p * c1.r) / (c1.r + c2.r);
ret = tangent_cp(c1, center);
}
if (abs(c1.r - c2.r) > eps) {
P out = (-c1.p * c2.r + c2.p * c1.r) / (c1.r - c2.r);
vector<L> nret = tangent_cp(c1, out);
ret.insert(ret.end(), ALL(nret));
}
else {
P v = c2.p - c1.p;
v /= abs(v);
P q1 = c1.p + v * P(0, 1) * c1.r;
P q2 = c1.p + v * P(0, -1) * c1.r;
ret.push_back(L{ q1, q1 + v });
ret.push_back(L{ q2, q2 + v });
}
return ret;
}
ld area(const VP &p) {//面積??
ld res = 0;
int n = p.size();
rep(j, n) res += cross(p[j], p[(j + 1) % n]);
return res / 2;
}
bool is_polygon(L l, VP &g) {
int n = g.size();
for (int i = 0; i < n; i++) {
P a = g[i];
P b = g[(i + 1) % n];
if (isis_ss(l, L{ a, b })) return true;
}
return false;
}
int is_in_Polygon(const VP &g, P p) {
bool in = false;
int n = g.size();
for (int i = 0; i < n; i++) {
P a = g[i] - p, b = g[(i + 1) % n] - p;
if (imag(a) > imag(b)) swap(a, b);
if (imag(a) <= 0 && 0 < imag(b))
if (cross(a, b) < 0) in = !in;
if (abs(cross(a, b)) < eps && dot(a, b) < eps) return 0; // on
}
if (in) return 1; // in
return -1; // out
}
VP ConvexHull(VP ps) {
int n = ps.size();
int k = 0;
sort(ps.begin(), ps.end());
VP ch(2 * n);
for (int i = 0; i < n; ch[k++] = ps[i++])
while (k >= 2 && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
for (int i = n - 2, t = k + 1; i >= 0; ch[k++] = ps[i--])
while (k >= t && ccw(ch[k - 2], ch[k - 1], ps[i]) <= 0) --k;
ch.resize(k - 1);
return ch;
}
VP ConvexCut(const VP &ps, L l) {
VP Q;
for (int i = 0; i < (int)ps.size(); i++) {
P A = ps[i], B = ps[(i + 1) % ps.size()];
if (ccw(l.a, l.b, A) != -1) Q.push_back(A);
if (ccw(l.a, l.b, A) * ccw(l.a, l.b, B) < 0)
Q.push_back(is_ll(L{ A, B }, l));
}
return Q;
}
//end of lib
int main() {
int n;
cin >> n;
vi a(n),b(n);
int x = 0;
rep(i, n) {
cin >> a[i];
x ^= a[i];
b[i] = a[i] ^ a[i] - 1;
}
sort(ALL(b), greater<>());
int c = 0;
rep(i, n) {
if (2 * x > b[i])x ^= b[i], c++;
}
if (x)c = -1;
cout << c << endl;
}
Submission Info
Submission Time |
|
Task |
C - Cheating Nim |
User |
vjudge1 |
Language |
C++14 (GCC 5.4.1) |
Score |
500 |
Code Size |
11923 Byte |
Status |
AC |
Exec Time |
45 ms |
Memory |
1024 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
500 / 500 |
Status |
|
|
Set Name |
Test Cases |
Sample |
example0.txt, example1.txt |
All |
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 |
AC |
1 ms |
256 KB |
001.txt |
AC |
1 ms |
256 KB |
002.txt |
AC |
45 ms |
1024 KB |
003.txt |
AC |
15 ms |
768 KB |
004.txt |
AC |
17 ms |
640 KB |
005.txt |
AC |
13 ms |
512 KB |
006.txt |
AC |
44 ms |
1024 KB |
007.txt |
AC |
44 ms |
1024 KB |
008.txt |
AC |
44 ms |
1024 KB |
009.txt |
AC |
44 ms |
1024 KB |
010.txt |
AC |
44 ms |
1024 KB |
011.txt |
AC |
44 ms |
1024 KB |
012.txt |
AC |
44 ms |
1024 KB |
013.txt |
AC |
44 ms |
1024 KB |
014.txt |
AC |
44 ms |
1024 KB |
015.txt |
AC |
44 ms |
1024 KB |
016.txt |
AC |
44 ms |
1024 KB |
017.txt |
AC |
44 ms |
1024 KB |
018.txt |
AC |
45 ms |
1024 KB |
019.txt |
AC |
44 ms |
1024 KB |
020.txt |
AC |
44 ms |
1024 KB |
021.txt |
AC |
5 ms |
256 KB |
022.txt |
AC |
5 ms |
384 KB |
023.txt |
AC |
42 ms |
1024 KB |
example0.txt |
AC |
1 ms |
256 KB |
example1.txt |
AC |
1 ms |
256 KB |