結果

問題 No.3249 AND
コンテスト
ユーザー jiangxinyang
提出日時 2025-08-07 14:16:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 2,234 bytes
コンパイル時間 715 ms
コンパイル使用メモリ 74,572 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-29 23:56:35
合計ジャッジ時間 2,257 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>

// 函数用于解决问题
void solve() {
    int n;
    std::cin >> n;
    std::vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    // 步骤 1: 预检查
    // 对于每个 i，b[i-1] 必须是 i 的子掩码。
    // (b[i-1] & i) 的结果中，为 1 的位一定是 i 和 b[i-1] 中都为 1 的位。
    // 如果 b[i-1] 是 i 的子掩码，这个结果应该等于 b[i-1]。
    for (int i = 1; i <= n; ++i) {
        if ((b[i - 1] & i) != b[i - 1]) {
            std::cout << -1 << std::endl;
            return;
        }
    }

    long long x = 0;
    // 最大值不超过 2*10^5，小于 2^18，所以检查到第 20 位足够了。
    const int MAX_BITS = 20;

    // 步骤 2: 逐位构造 x
    for (int k = 0; k < MAX_BITS; ++k) {
        bool must_be_one = false;
        bool must_be_zero = false;

        for (int i = 1; i <= n; ++i) {
            // 获取 i 和 b[i-1] 的第 k 位
            bool i_k = (i >> k) & 1;
            bool b_ik = (b[i - 1] >> k) & 1;

            if (b_ik) {
                // 如果 b[i-1] 的第 k 位为 1，则 x 的第 k 位必须为 1
                // (预检查已保证此时 i_k 也为 1)
                must_be_one = true;
            } else { // b[i-1] 的第 k 位为 0
                if (i_k) {
                    // 如果 i 的第 k 位为 1，而 b[i-1] 的第 k 位为 0，
                    // 则 x 的第 k 位必须为 0
                    must_be_zero = true;
                }
            }
        }

        // 检查是否存在矛盾
        if (must_be_one && must_be_zero) {
            std::cout << -1 << std::endl;
            return;
        }

        // 如果 x 的第 k 位必须为 1，则设置它
        if (must_be_one) {
            x |= (1LL << k);
        }
    }

    // 步骤 3: 最终检查
    // 如果构造出的最小非负 x 是 0，但题目要求正整数，则无解。
    if (x == 0) {
        std::cout << -1 << std::endl;
    } else {
        std::cout << x << std::endl;
    }
}

int main() {
    // 加速 C++ IO
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}
0