結果

問題 No.2977 Kth Xor Pair
ユーザー ooaiu
提出日時 2024-12-03 15:40:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,398 bytes
コンパイル時間 3,671 ms
コンパイル使用メモリ 264,272 KB
実行使用メモリ 87,808 KB
最終ジャッジ日時 2024-12-03 15:42:01
合計ジャッジ時間 66,491 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

template <int B = 31, class U = uint64_t, class ST = int>
struct BinaryTrie {
   private:
    struct node;
    using np = std::unique_ptr<node>;
    struct node {
        std::array<np, 2> ch;
        ST count;
        node() : ch{nullptr, nullptr}, count(0) {}
    };
    np root = std::make_unique<node>();
    const U MAX;
    np& get(const np& t, bool f) {
        if (!t->ch[f]) t->ch[f] = std::make_unique<node>();
        return t->ch[f];
    }
    void add(const np& t, const U& x, ST n, int log = B - 1) {
        t->count += n;
        if (log < 0) return;
        bool f = (x >> log) & 1;
        add(get(t, f), x, n, log - 1);
    }
    U kth_element(const np& t, ST k, U xor_val, int log = B - 1) const {
        if (log < 0) return 0;
        bool f = (xor_val >> log) & 1;
        ST sz = t->ch[f] ? t->ch[f]->count : 0;
        if (k < sz)
            return kth_element(t->ch[f], k, xor_val, log - 1);
        else
            return kth_element(t->ch[f ^ 1], k - sz, xor_val, log - 1) | U(1) << log;
    }
    ST count_lt(const np& t, const U& x, U xor_val, int log = B - 1) const {
        if (!t || log < 0) return 0;
        bool f = (xor_val >> log) & 1;
        bool g = (x >> log) & 1;
        if (g == 0) return count_lt(t->ch[f], x, xor_val, log - 1);
        ST res = t->ch[f] ? t->ch[f]->count : 0;
        res += count_lt(t->ch[f ^ 1], x, xor_val, log - 1);
        return res;
    }

   public:
    BinaryTrie() : MAX((U(1) << B) - 1) {}
    void add(const U& x, int n = 1) {
        assert(0 <= x && x <= MAX);
        add(root, x, n, B - 1);
    }
    U kth_element(ST k, U xor_val = 0) const {
        assert(root && 0 <= k && k < root->count);
        return kth_element(root, k, xor_val);
    }
    U get_min(U xor_val = 0) const {
        assert(root && root->count);
        return kth_element(0, xor_val);
    }
    U get_max(U xor_val = 0) const {
        assert(root && root->count);
        return kth_element((root->count) - 1, xor_val);
    }
    ST count_lt(const U& x, U xor_val = 0) const {
        return count_lt(root, x, xor_val);
    }
    ST count_le(const U& x, U xor_val = 0) const {
        if (x == MAX) return root->count;
        return count_lt(x + 1, xor_val);
    }
    ST count_gt(const U& x, U xor_val = 0) const {
        if (x == MAX) return 0;
        return root->count - count_le(x, xor_val);
    }
    ST count_ge(const U& x, U xor_val = 0) const {
        if (x == 0) return root->count;
        return root->count - count_lt(x, xor_val);
    }
};

void solve() {
    int N;
    int64_t K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    BinaryTrie<31, uint64_t, int64_t> trie;
    for (int i = 0; i < N; i++) trie.add(A[i]);
    const auto check = [&](int x) -> bool {
        int64_t res = 0;
        for (int i = 0; i < N; i++) {
            res += trie.count_le(x, A[i]) - 1;
        }
        res >>= 1;
        return res >= K;
    };
    int lo = 0, hi = (1LL << 31) - 1;
    while (hi > lo + 1) {
        int mi = lo + ((hi - lo) >> 1);
        (check(mi) ? hi : lo) = mi;
    }
    cout << hi << endl;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int tt = 1;
    // std::cin >> tt;
    while (tt--) {
        solve();
    }
}
0