Untitled
unknown
c_cpp
a year ago
5.0 kB
5
Indexable
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; using db = long double; template <typename T> struct point { T x, y; point() { x = 0; y = 0; } point(const T &_x, const T &_y) { x = _x; y = _y; } point(const point &a, const point &b) { x = b.x - a.x; y = b.y - a.y; } point operator+(const point &other) { return point(x + other.x, y + other.y); } point operator-(const point &other) { return point(x - other.x, y - other.y); } T operator*(const point &other) { return x * other.x + y * other.y; } T operator%(const point &other) { return x * other.y - other.x * y; } }; template <typename T> istream& operator>>(istream& in, point<T> &p) { in >> p.x >> p.y; return in; } using pt = point<ll>; db PolarAngle(pt p) { return atan2((db)p.y, (db)p.x); } bool cmp(pt a, pt b) { return PolarAngle(a) < PolarAngle(b); } constexpr int N = 1e4; int grundy[N + 1]; void calc() { grundy[0] = 0; for (int i = 1; i <= N; i++) { bitset<1000> used; used[grundy[i - 1]] = 1; for (int j = 0; 2 * j <= i - 2; j++) { used[grundy[j] ^ grundy[i - 2 - j]] = 1; } grundy[i] = 0; while (used[grundy[i]]) { grundy[i]++; } } } struct segtree { struct node { int pref, suf, gr, sz; }; node combine(node a, node b) { if (b.sz == 0) return a; int pref = a.pref; if (a.pref == a.sz) { pref = a.pref + b.pref; } int suf = b.suf; if (b.suf == b.sz) { suf = b.suf + a.suf; } int gr = a.gr ^ b.gr; if (a.suf != a.sz && b.pref != b.sz) { gr ^= grundy[a.suf + b.pref]; } return { pref, suf, gr, a.sz + b.sz }; } node one_element(int x) { return { x, x, 0, 1 }; } int size; vector<node> tree; void init(int n) { size = 1; while (size < n) size *= 2; tree.assign(2 * size - 1, {0, 0, 0, 0}); } void set(int i, int v, int x, int lx, int rx) { if (rx - lx == 1) { tree[x] = one_element(v); } else { int m = (lx + rx) / 2; if (i < m) { set(i, v, x * 2 + 1, lx, m); } else { set(i, v, x * 2 + 2, m, rx); } tree[x] = combine(tree[x * 2 + 1], tree[x * 2 + 2]); } } void set(int i, int v) { set(i, v, 0, 0, size); } int get() { int res = tree[0].gr; if (tree[0].pref == tree[0].sz) { return (grundy[tree[0].sz - 2] == 0 ? 1 : 0); } res ^= grundy[tree[0].pref + tree[0].suf]; return res; } }; void test_case() { calc(); int n, m, q; cin >> n >> m >> q; pt C; cin >> C; vector<pt> pts(n); for (int i = 0; i < n; i++) { cin >> pts[i]; pts[i] = pts[i] - C; } sort(pts.begin(), pts.end(), cmp); segtree tr; tr.init(n); for (int i = 0; i < n; i++) { tr.set(i, 0); } vector<int> cnt(n); auto add = [&](db pa, int x) -> void { if (pa < PolarAngle(pts[0])) { cnt[n - 1] += x; if (cnt[n - 1] == 0 && x == -1) { tr.set(n - 1, 0); } if (cnt[n - 1] == 1) { tr.set(n - 1, 1); } return; } int L = 0, R = n; while (L + 1 != R) { int M = (L + R) / 2; if (PolarAngle(pts[M]) <= pa) { L = M; } else { R = M; } } cnt[L] += x; if (cnt[L] == 0 && x == -1) { tr.set(L, 0); } if (cnt[L] == 1) { tr.set(L, 1); } }; for (int i = 0; i < m; i++) { pt M; cin >> M; M = M - C; add(PolarAngle(M), 1); } cout << (tr.get() != 0 ? "Alice\n" : "Bob\n"); while (q--) { char t; cin >> t; pt M; cin >> M; M = M - C; if (t == '+') { add(PolarAngle(M), 1); } else { add(PolarAngle(M), -1); } cout << (tr.get() != 0 ? "Alice\n" : "Bob\n"); } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int tests = 1; // cin >> tests; while (tests--) { test_case(); } return 0; }
Editor is loading...
Leave a Comment