結果

問題 No.3258 Xor Division Game
ユーザー lif4635
提出日時 2025-09-05 18:28:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,129 bytes
コンパイル時間 3,857 ms
コンパイル使用メモリ 298,068 KB
実行使用メモリ 814,584 KB
最終ジャッジ日時 2025-09-05 21:16:49
合計ジャッジ時間 8,251 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other MLE * 1 -- * 66
権限があれば一括ダウンロードができます

ソースコード

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("out2.txt", "w", stdout);

    //map, setでlogを余分につけたので、時間計算量 O(N log^2 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の生成に利用する
    auto f = [&](auto f, int l, int r, map<int, int> cnt, set<int> goods) -> int {
        if (l == r) return 0;

        if (goods.empty()) return r - l;

        int m = *goods.begin();
        // cout << l << " " << r << " " << m << endl;

        cnt[B[m]]--;
        goods.erase(m);

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

        map<int, int> cnt_sh;
        rep(i, sh.l, sh.r) cnt_sh[B[i]]++;
        set<int> goods_sh;
        rep(i, sh.l, sh.r) if (cnt_sh[B[i]]) goods_sh.insert(i);

        int result_sh = f(f, sh.l, sh.r, cnt_sh, goods_sh);

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

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

        return result_sh + result_lo;
    };

    map<int, int> cnt;
    rep(i, 0, N) cnt[B[i]]++;
    set<int> goods;
    rep(i, 0, N) if (cnt[B[i]] == 1) goods.insert(i);
    int ans = f(f, 0, N, cnt, goods);

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