結果

問題 No.3046 White Tiger vs Monster
ユーザー 👑 potato167
提出日時 2025-03-24 19:28:46
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,487 bytes
コンパイル時間 2,301 ms
コンパイル使用メモリ 202,496 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2025-03-24 19:28:57
合計ジャッジ時間 9,270 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 68 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(p) p.begin(), p.end()

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    ll B;
    cin >> B;
    auto f = [&](ll a) -> int {
        int res = 0;
        while (a >= (1ll << (res + 1))) res++;
        return res;
    };
    vector<ll> X, Y;
    auto k = f(B);
    rep(i, 0, N){
        ll a;
        cin >> a;
        int d = f(a);
        if (d == k) X.push_back(a);
        else if (d < k) Y.push_back(a);
    }
    int ans = (int)Y.size();
    if (X.empty()){
        cout << ans << "\n";
        return 0;
    }
    sort(all(X));
    sort(all(Y));
    if (Y.empty()){
        cout << ans + (X[0] <= B) << "\n";
        return 0;
    }
    ll mask = 0;
    for (auto y : Y) mask ^= y;
    if (X[0] <= (mask ^ B)){
        cout << ans + 1 << "\n";
        return 0;
    }
    vector<int> P(X.size()), Q(Y.size());
    rep(i, 0, X.size()){
        ll tmp = (mask ^ B ^ X[i]);
        int d = f(tmp);
        P[i] = upper_bound(all(Y), 1ll << d) - Y.begin();
    }
    rep(i, 0, Y.size()){
        ll tmp = (mask ^ B ^ Y[i]);
        Q[i] = upper_bound(all(X), tmp) - X.begin();
        if (i) Q[i] = max(Q[i], Q[i - 1]);
    }
    rep(i, 0, X.size()){
        if (P[i] != 0 && i < Q[P[i] - 1]){
            cout << ans + 1 << "\n";
            return 0;
        }
    }
    cout << ans << "\n";
}
0