結果

問題 No.3258 Xor Division Game
ユーザー lif4635
提出日時 2025-09-05 18:32:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,583 bytes
コンパイル時間 4,022 ms
コンパイル使用メモリ 291,128 KB
実行使用メモリ 63,864 KB
最終ジャッジ日時 2025-09-05 21:17:09
合計ジャッジ時間 17,682 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 49 WA * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i, l, r) for (int i = (int)(l); i < (int)(r); i++)
#define all(x) (x).begin(), (x).end()
#define siz(x) (int)(x).size()

//座標圧縮を行う関数
template<class T>
vector<int> compress(vector<T> A) {
    int N = siz(A);
    vector<T> B = A;
    sort(B.begin(), B.end());
    vector<int> ret(N);
    rep(i, 0, N) {
        ret[i] = lower_bound(all(B), A[i]) - B.begin();
    }
    return ret;
}

struct interval {
    int l, r;
};

int main() {

    // freopen("in.txt", "r", stdin);
    // freopen("out1.txt", "w", stdout);

    //頑張って配列で管理しているので、時間計算量 O(N log N) 空間計算量 O(N log N)

    int N; cin >> N;
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    //座標圧縮
    vector<int> B = compress(A);

    //短いほうのcntの生成に利用する
    //高々18個
    vector<vector<int>> cnt(20, vector<int>(N, 0));
    auto f = [&](auto f, int l, int r, int id, vector<int>& goods) -> int {
        // cout << l << " " << r << " " << id << endl;
        if (l == r) return 0;

        int m = -1;
        //goodsには0も紛れ込む可能性があるので、排除する。
        while(!goods.empty()) {
            if (cnt[id][B[goods.back()]] == 1) {
                m = goods.back();
                break;
            }
            goods.pop_back();
        }

        if (m == -1) return r - l;

        cnt[id][B[m]]--;

        //short, long
        interval sh = {l, m}, lo = {m+1, r};
        if (m - l > r - (m + 1)) swap(sh, lo);

        rep(i, sh.l, sh.r) cnt[id+1][B[i]]++;

        vector<int> goods_sh;
        rep(i, sh.l, sh.r) if (cnt[id+1][B[i]]) goods_sh.push_back(i);

        int result_sh = f(f, sh.l, sh.r, id+1, goods_sh);

        //再利用するので、必要なくなったら0埋めされた状態に戻しておく
        rep(i, sh.l, sh.r) cnt[id+1][B[i]]--;

        //短いほうの区間 [sh.l, sh.r) がなくなった分を cnt, goods に差分更新する
        rep(i, sh.l, sh.r) cnt[id][B[i]]--;
        rep(i, sh.l, sh.r) if (cnt[id][B[i]] == 1) goods.push_back(i);

        int result_lo = f(f, lo.l, lo.r, id, goods);

        return result_sh + result_lo;
    };

    rep(i, 0, N) cnt[0][B[i]]++;
    vector<int> goods;
    rep(i, 0, N) if (cnt[0][B[i]] == 1) goods.push_back(i);
    // cout << siz(goods) << endl;
    int ans = f(f, 0, N, 0, goods);
    // cout << "ans = " << ans << endl;

    int turn = N - ans;
    cout << (turn%2? "Alice" : "Bob") << endl;
}
0