結果

問題 No.3046 White Tiger vs Monster
ユーザー Naru820
提出日時 2025-03-22 20:34:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,826 bytes
コンパイル時間 3,426 ms
コンパイル使用メモリ 278,544 KB
実行使用メモリ 7,328 KB
最終ジャッジ日時 2025-03-22 22:33:31
合計ジャッジ時間 11,879 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 72 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using ll = long long;

ll n,b,a[200000],d,g[60][60];
int main(){
    cin >> n >> b;
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 60; i >= 0; i--){
        if((1ll << i) & b){
            d = i;
            break;
        }
    }
    vector<ll> eq,low;
    for(int i = 0; i < n; i++){
        int tmp = 0;
        for(int j = 60; j >= 0; j--){
            if((1ll << j) & a[i]){
                tmp = j;
                break;
            }
        }
        if(tmp == d){
            eq.eb(a[i]);
        }
        if(tmp < d){
            low.eb(a[i]);
        }
    }
    for(int i = 0; i < d; i++){
        for(int j = 0; j < d; j++) g[i][j] = 1;
    }
    for(int i = 0; i < low.size(); i++){
        b ^= low[i];
        int tmp = 0;
        for(int j = 60; j >= 0; j--){
            if(low[i] & (1ll << j)){
                tmp = j;
                break;
            }
        }
        for(int j = 0; j < tmp; j++){
            if((~low[j]) >> (j & 1)){
                g[j][tmp] = 1;
            }
        }
    }
    for(int k = 0; k < d; k++){
        for(int i = 0; i < d; i++){
            for(int j = 0; j < d; j++){
                g[i][j] |= (g[i][k] & g[k][j]);
            }
        }
    }
    for(int i = 0; i < eq.size(); i++){
        if((b ^ eq[i]) == 0){
            cout << low.size() + 1;
            return 0;
        }
        ll tmp = b ^eq[i],e = 0;
        for(int j = 60; j >= 0; j--){
            if((tmp & (1ll << j))){
                e = j;
                break;
            }
        }
        for(int j = e; j < d; j++){
            if((~eq[i]) >> (j & 1 & g[e][j])){
                cout << low.size() + 1;
                return 0;
            }
        }
    }
    
    cout << low.size() << endl;
}
0