Submission #70104098

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<long long, long long>;
using vpll = vector<pll>;
using mint = modint1000000007;
const long double EPS = 1e-18;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<ll>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<long long, long long>;
using vpll = vector<pll>;
using mint = modint1000000007;
const long double EPS = 1e-18;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                      \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);

// custom hash to avoid hacking and speed up unordered_map
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return (size_t)splitmix64(x + FIXED_RANDOM);
    }
};

ll Xg, Yg;
unordered_map<ll, int, custom_hash> memo;

// forbidden landing positions: multiples of X or Y (including 0)
inline bool is_forbidden(ll v) {
    // v is non-negative (we only call on targets >= 0)
    return (v % Xg == 0) || (v % Yg == 0);
}

// compute grundy for position pos (pos >= 0), iterative with memoization
int compute_grundy(ll pos) {
    if (pos == 0) return 0;
    auto it0 = memo.find(pos);
    if (it0 != memo.end()) return it0->second;

    // explicit stack for DFS-like dependency resolution
    vector<ll> stk;
    stk.push_back(pos);

    while (!stk.empty()) {
        ll v = stk.back();
        if (memo.find(v) != memo.end()) {
            stk.pop_back();
            continue;
        }

        bool can1 = (v >= 1) && !is_forbidden(v - 1);
        bool can2 = (v >= 2) && !is_forbidden(v - 2);

        if (!can1 && !can2) {
            memo[v] = 0;
            stk.pop_back();
            continue;
        }

        // collect dependencies that must be computed first
        vector<ll> deps;
        auto add_deps_for_target = [&](ll t) {
            if (t <= 0) return; // t==0 is forbidden (multiple), but kept for safety
            ll a = (t / Xg) * Xg;
            ll b = (t / Yg) * Yg;
            ll f = max(a, b); // largest forbidden <= t
            if (t >= f + 3) {
                if (memo.find(f + 1) == memo.end()) deps.push_back(f + 1);
                if (memo.find(f + 2) == memo.end()) deps.push_back(f + 2);
            } else {
                if (memo.find(t) == memo.end()) deps.push_back(t);
            }
        };

        if (can1) add_deps_for_target(v - 1);
        if (can2) add_deps_for_target(v - 2);

        bool pushed = false;
        for (ll d : deps) {
            if (memo.find(d) == memo.end()) {
                stk.push_back(d);
                pushed = true;
            }
        }
        if (pushed) continue; // process dependencies first

        // all dependencies are computed -> compute g(v)
        bool seen[4] = {false, false, false, false};

        auto resolve_gt = [&](ll t) -> int {
            // t is >=1 and not forbidden
            if (t == 0) return 0; // safety (shouldn't be used)
            ll a = (t / Xg) * Xg;
            ll b = (t / Yg) * Yg;
            ll f = max(a, b);
            if (t >= f + 3) {
                int g1 = memo[f + 1];
                int g2 = memo[f + 2];
                bool used[4] = {false, false, false, false};
                if (0 <= g1 && g1 < 4) used[g1] = true;
                if (0 <= g2 && g2 < 4) used[g2] = true;
                int g3 = 0; while (used[g3]) ++g3;
                int idx = (int)((t - (f + 1)) % 3LL);
                if (idx == 0) return g1;
                if (idx == 1) return g2;
                return g3;
            } else {
                return memo[t];
            }
        };

        if (can1) {
            int gt = resolve_gt(v - 1);
            if (0 <= gt && gt < 4) seen[gt] = true;
        }
        if (can2) {
            int gt = resolve_gt(v - 2);
            if (0 <= gt && gt < 4) seen[gt] = true;
        }

        int g = 0; while (g < 4 && seen[g]) ++g;
        memo[v] = g;
        stk.pop_back();
    }

    return memo[pos];
}

void solve() {
    int n;
    ll X, Y;
    cin >> n >> X >> Y;
    Xg = X; Yg = Y;

    vector<ll> orig(n);
    for (int i = 0; i < n; ++i) cin >> orig[i];

    // frequency map: only compute grundy for unique positions. Because XOR with duplicate
    // appears with parity, we only need odd counts.
    unordered_map<ll, int, custom_hash> freq;
    freq.reserve(n * 2 + 10);
    for (ll v : orig) {
        freq[v] ^= 1; // keep parity only (0 or 1)
    }

    memo.clear();
    memo.reserve((size_t)(freq.size() * 3 + 1024));
    memo[0] = 0;

    int xorsum = 0;
    for (auto &kv : freq) {
        if (kv.second == 0) continue; // even occurrences cancel out
        ll v = kv.first;
        int g = compute_grundy(v);
        xorsum ^= g;
    }

    if (xorsum != 0) cout << "Alice\n";
    else cout << "Bob\n";
}

int main() {
    INIT;
    ios::fmtflags f = cout.flags(); (void)f;
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Submission Info

Judge Result