結果

問題 No.2844 Birthday Party Decoration
ユーザー InTheBloomInTheBloom
提出日時 2024-08-23 22:20:14
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,358 bytes
コンパイル時間 996 ms
コンパイル使用メモリ 91,420 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-08-23 22:20:17
合計ジャッジ時間 2,055 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;
using ll = long long;

constexpr ll llINF = 1'000'000'000'000'000'000;

int main () {
    // 各bitで最短距離の店を割り出すと、右側と(存在すれば)左側に候補がある。
    // 各ケースO(N^2)個の右左の行き方を探索すれば十分

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

        vector<ll> left(N), right(N);
        // 右側候補、左側候補を見つける。
        for (int i = 0; i < N; i++) {
            if (0 < (X & (1LL << c[i]))) {
                left[i] = right[i] = 0;
                continue;
            }

            // 左側(存在しない場合アリ)
            [&] () {
                if (X < (1LL << c[i])) {
                    left[i] = llINF;
                    return;
                }

                ll mask = (1LL << c[i]) - 1;
                left[i] = (X & mask) + 1;
            }();

            // 右側(必ず存在)
            {
                ll mask = (1LL << c[i]) - 1;
                right[i] = (1LL << c[i]) - (mask & X);
            }
        }

        // O(N^2)個の候補を探索
        ll ans = llINF;
        ll all = 0;
        for (int i = 0; i < N; i++) all |= (1LL << c[i]);

        ll max_left = -1;
        for (int i = 0; i < N; i++) max_left = max(max_left, left[i]);
        if (max_left < llINF) ans = min(ans, 2 * max_left);

        ll max_right = -1;
        for (int i = 0; i < N; i++) max_right = max(max_right, right[i]);
        ans = min(ans, 2 * max_right);

        for (int i = 0; i < N; i++) {
            if (left[i] == llINF) continue;

            for (int j = 0; j < N; j++) {
                ll cur = 0;
                for (int k = 0; k < N; k++) {
                    if (left[k] <= left[i]) cur |= (1LL << c[k]);
                    if (right[k] <= right[j]) cur |= (1LL << c[k]);
                }

                if (all == cur) {
                    ll cost = 0;
                    cost += 2 * left[i];
                    cost += 2 * right[j];

                    ans = min(ans, cost);
                }
            }
        }

        assert(0 <= ans);
        cout << ans << "\n";
    }
}
0