Submission #70104136

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);
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}

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

inline bool is_forbidden(ll v) {
    return (v > 0) && ((v % Xg == 0) || (v % Yg == 0));
}

int compute_grundy(ll k) {
    if (k == 0) return 0;
    if (memo.count(k)) return memo[k];

    vector<ll> stk;
    stk.push_back(k);

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

        bool can1 = (v >= 1) && !is_forbidden(v - 1);
        bool can2 = (v >= 2) && !is_forbidden(v - 2);
        
        vector<ll> deps;
        auto add_deps = [&](ll t) {
            if (t == 0) return;
            ll f = max((t / Xg) * Xg, (t / Yg) * Yg);
            if (t >= f + 3) {
                if (!memo.count(f + 1)) deps.push_back(f + 1);
                if (!memo.count(f + 2)) deps.push_back(f + 2);
            } else {
                if (!memo.count(t)) deps.push_back(t);
            }
        };

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

        bool pushed = false;
        for (ll d : deps) {
            if (!memo.count(d)) {
                stk.push_back(d);
                pushed = true;
            }
        }
        if (pushed) continue;

        auto resolve = [&](ll t) -> int {
            if (t == 0) return 0;
            ll f = max((t / Xg) * Xg, (t / Yg) * Yg);
            if (t >= f + 3) {
                int g1 = memo.at(f + 1);
                int g2 = memo.at(f + 2);
                set<int> s = {g1, g2};
                int g3 = 0;
                while (s.count(g3)) g3++;
                ll dist = t - (f + 1);
                if (dist % 3 == 0) return g1;
                if (dist % 3 == 1) return g2;
                return g3;
            }
            return memo.at(t);
        };
        
        set<int> seen;
        if (can1) seen.insert(resolve(v - 1));
        if (can2) seen.insert(resolve(v - 2));
        
        int g = 0;
        while (seen.count(g)) g++;
        memo[v] = g;
        stk.pop_back();
    }
    return memo[k];
}

void solve() {
    ll n, X, Y;
    cin >> n >> X >> Y;
    Xg = X; Yg = Y;
    memo.clear();
    
    map<ll, int> counts;
    rep(i, n) {
        ll val;
        cin >> val;
        counts[val]++;
    }
    
    int nim_sum = 0;
    for(auto const& [val, count] : counts) {
        if (count % 2 == 1) {
            nim_sum ^= compute_grundy(val);
        }
    }

    if (nim_sum != 0) cout << "Alice" << endl;
    else cout << "Bob" << endl;
}

int main() {
    INIT;
    ll T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Submission Info

Judge Result