結果

問題 No.2977 Kth Xor Pair
コンテスト
ユーザー bal4u
提出日時 2025-02-16 19:24:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,354 ms / 3,000 ms
コード長 1,887 bytes
コンパイル時間 1,715 ms
コンパイル使用メモリ 197,432 KB
実行使用メモリ 55,048 KB
最終ジャッジ日時 2025-02-16 19:24:52
合計ジャッジ時間 28,882 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
static const int BITS = 31;
 
struct Node {
    int child[2];
    int cnt;
    Node() : cnt(0) {
        child[0] = child[1] = -1;
    }
};
 
vector<Node> trie;
 
void initTrie(){
    trie.clear();
    trie.push_back(Node());
}
 
void insertNum(int num){
    int node = 0;
    trie[node].cnt++;
    for (int bit = BITS; bit >= 0; bit--){
        int b = (num >> bit) & 1;
        if(trie[node].child[b] == -1){
            trie[node].child[b] = trie.size();
            trie.push_back(Node());
        }
        node = trie[node].child[b];
        trie[node].cnt++;
    }
}
 
inline ll queryNum(int num, int X){
    int node = 0;
    ll res = 0;
    for (int bit = BITS; bit >= 0; bit--){
        if(node == -1) break;
        int a_bit = (num >> bit) & 1;
        int x_bit = (X >> bit) & 1;
        if(x_bit == 1){
            int next = trie[node].child[a_bit];
            if(next != -1)
                res += trie[next].cnt;
            node = trie[node].child[1 - a_bit];
        } else {
            node = trie[node].child[a_bit];
        }
    }
    if(node != -1) res += trie[node].cnt;
    return res;
}
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int N;
    ll K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i=0; i<N; i++){
        cin >> A[i];
    }
 
    initTrie();
    for (int a : A){
        insertNum(a);
    }
 
    ll low = 0, high = (1LL << (BITS+1)) - 1, ans = 0;
    while(low <= high){
        int mid = (low + high) / 2;
        ll total = 0;
        for (int a : A){
            ll cnt = queryNum(a, mid);
            total += (cnt - 1);
        }
        total /= 2;
 
        if(total >= K){
            ans = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
 
    cout << ans << "\n";
    return 0;
}
0