結果

問題 No.2844 Birthday Party Decoration
ユーザー Today03
提出日時 2024-08-23 22:22:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,299 bytes
コンパイル時間 1,939 ms
コンパイル使用メモリ 198,024 KB
最終ジャッジ日時 2025-02-23 23:59:04
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 10;
const ll INFL = 4e18;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int N;
        ll X;
        cin >> N >> X;
        vector<int> C(N);
        for (int i = 0; i < N; i++) cin >> C[i];

        ll ans = INFL;

        int hi = -1;
        for (int i = N - 1; i >= 0; i--) {
            if (!(X >> C[i] & 1)) {
                hi = C[i];
                break;
            }
        }

        if (hi != -1) {
            ll lo = X - 1, hi = INFL;
            while (hi - lo > 1) {
                ll mid = (hi + lo) / 2;

                int dif = -1;
                for (int i = 60; i >= 0; i--) {
                    if ((mid >> i & 1) != (X >> i & 1)) {
                        dif = i;
                        break;
                    }
                }

                vector<int> need;
                for (int i = 0; i < N; i++) {
                    if (!(X >> C[i] & 1)) {
                        need.push_back(C[i]);
                    }
                }

                if (!need.empty() && need.back() > dif) {
                    lo = mid;
                } else {
                    hi = mid;
                }
            }
            ans = min(ans, 2ll * abs(X - hi));
        }

        if (hi == -1) {
            ans = 0;
        }

        int lowest_bit = -1;
        for (int i = 0; i < 60; i++) {
            if (X >> i & 1) {
                lowest_bit = i;
                break;
            }
        }

        int hi2 = -1;
        for (int i = N - 1; i >= 0; i--) {
            if (C[i] < lowest_bit && !(X >> C[i] & 1)) {
                hi2 = C[i];
                break;
            }
        }

        if (hi2 != -1 && lowest_bit >= C.back()) {
            ll goal = 0;
            for (int i = 0; i < 60; i++) {
                if (i < hi2) {
                    continue;
                } else if (i < lowest_bit) {
                    goal |= 1ll << i;
                } else if (i == lowest_bit) {
                    continue;
                } else if (X >> i & 1) {
                    goal |= 1ll << i;
                }
            }
            ans = min(ans, abs(X - goal) * 2);
        }

        cout << ans << endl;
    }
}
0