結果

問題 No.2977 Kth Xor Pair
ユーザー iseeisee
提出日時 2024-12-03 19:52:53
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,220 ms / 3,000 ms
コード長 2,481 bytes
コンパイル時間 1,859 ms
コンパイル使用メモリ 131,612 KB
実行使用メモリ 83,084 KB
最終ジャッジ日時 2024-12-03 19:53:11
合計ジャッジ時間 16,849 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

// https://yukicoder.me/submissions/1029779
#include <iostream>
#include <vector>
#include <cmath>
#include <utility>
#include <algorithm>
using namespace std;

// Function to count 0s and 1s in bit position `i`
pair<long long, long long> count01(const vector<long long>& L, long long i) {
    long long czero = 0, cone = 0;
    for (long long a : L) {
        if ((a >> i) & 1) {
            cone++;
        } else {
            czero++;
        }
    }
    return {czero, cone};
}

// Function to divide the list into 0-group and 1-group based on bit position `i`
pair<vector<long long>, vector<long long>> div01(const vector<long long>& L, long long i) {
    vector<long long> rzero, rone;
    for (long long a : L) {
        if ((a >> i) & 1) {
            rone.push_back(a);
        } else {
            rzero.push_back(a);
        }
    }
    return {rzero, rone};
}

signed main() {
    // Input
    long long N, K;
    cin >> N >> K;
    vector<long long> A(N);
    for (long long i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Calculation & Output
    K--;
    K *= 2;
    K += N;

    vector<pair<vector<long long>, vector<long long>>> pairs = {{A, A}};
    long long ans = 0;

    for (long long i = 29; i >= 0; --i) {
        ans <<= 1;
        long long czero = 0;

        for (auto& p : pairs) {
            auto [lz, lo] = count01(p.first, i);
            auto [rz, ro] = count01(p.second, i);
            czero += lz * rz + lo * ro;
        }

        vector<pair<vector<long long>, vector<long long>>> npairs;

        if (K >= czero) {
            ans += 1;
            K -= czero;

            for (auto& p : pairs) {
                auto [lz, lo] = div01(p.first, i);
                auto [rz, ro] = div01(p.second, i);
                if (!lz.empty() && !ro.empty()) {
                    npairs.push_back({lz, ro});
                }
                if (!lo.empty() && !rz.empty()) {
                    npairs.push_back({lo, rz});
                }
            }
        } else {
            for (auto& p : pairs) {
                auto [lz, lo] = div01(p.first, i);
                auto [rz, ro] = div01(p.second, i);
                if (!lz.empty() && !rz.empty()) {
                    npairs.push_back({lz, rz});
                }
                if (!lo.empty() && !ro.empty()) {
                    npairs.push_back({lo, ro});
                }
            }
        }

        pairs = npairs;
    }

    cout << ans << endl;
    return 0;
}
0