結果

問題 No.2977 Kth Xor Pair
ユーザー ooaiuooaiu
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 6 ms
5,248 KB
testcase_03 AC 6 ms
5,248 KB
testcase_04 AC 6 ms
5,248 KB
testcase_05 AC 6 ms
5,248 KB
testcase_06 AC 5 ms
5,248 KB
testcase_07 AC 1,332 ms
53,248 KB
testcase_08 AC 2,892 ms
83,968 KB
testcase_09 AC 2,744 ms
80,000 KB
testcase_10 AC 2,712 ms
81,152 KB
testcase_11 AC 2,931 ms
83,072 KB
testcase_12 AC 2,720 ms
81,280 KB
testcase_13 TLE -
testcase_14 AC 1,329 ms
52,480 KB
testcase_15 AC 2,655 ms
75,904 KB
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 AC 2,994 ms
87,680 KB
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 AC 508 ms
7,936 KB
testcase_28 AC 303 ms
7,936 KB
testcase_29 AC 386 ms
7,936 KB
testcase_30 AC 425 ms
8,064 KB
testcase_31 AC 390 ms
8,192 KB
testcase_32 AC 225 ms
5,248 KB
testcase_33 AC 241 ms
5,248 KB
testcase_34 AC 242 ms
5,248 KB
testcase_35 AC 242 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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