結果

問題 No.2977 Kth Xor Pair
コンテスト
ユーザー bal4u
提出日時 2025-02-16 19:21:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,886 bytes
コンパイル時間 2,079 ms
コンパイル使用メモリ 196,340 KB
実行使用メモリ 55,152 KB
最終ジャッジ日時 2025-02-16 19:21:23
合計ジャッジ時間 10,464 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other WA * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:73:28: warning: left shift count >= width of type [-Wshift-count-overflow]
   73 |     int low = 0, high = (1 << (BITS+1)) - 1, ans = 0;
      |                          ~~^~~~~~~~~~~

ソースコード

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);
    }
 
    int low = 0, high = (1 << (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