結果

問題 No.2977 Kth Xor Pair
ユーザー kwm_t
提出日時 2024-12-01 01:37:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,565 ms / 3,000 ms
コード長 4,597 bytes
コンパイル時間 2,932 ms
コンパイル使用メモリ 255,824 KB
実行使用メモリ 71,216 KB
最終ジャッジ日時 2024-12-01 01:38:39
合計ジャッジ時間 33,494 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r) - 1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
struct BinaryTrie {
    int kind;
    std::vector<int>node;
    std::vector<std::array<int, 2>>next;
    std::array<int, 2> e{ -1,-1 };
    BinaryTrie(int _kind) :kind(_kind) {
        node.resize(1);
        next.emplace_back(e);
    }
    void insert(const std::vector<int>&v) {
        int now = 0;
        for (int i = 0; i < v.size(); ++i) {
            if (-1 == next[now][v[i]]) {
                next[now][v[i]] = node.size();
                node.emplace_back(0);
                next.emplace_back(e);
            }
            now = next[now][v[i]];
            node[now]++;
        }
    }
    // 1-indexed
    std::vector<int>kth_element(int k) {
        int now = 0;
        std::vector<int>ret;
        while (true) {
            bool flag = false;
            for (int i = 0; i < kind; ++i) {
                if (-1 == next[now][i])continue;
                if (k <= node[next[now][i]]) {
                    flag = true;
                    ret.emplace_back(i);
                    now = next[now][i];
                    break;
                }
                else {
                    k -= node[next[now][i]];
                }
            }
            if (!flag)break;
        }
        return ret;
    }
    bool seach(const std::vector<int>&v) {
        int now = 0;
        for (int i = 0; i < (int)v.size(); ++i) {
            if (-1 == next[now][v[i]])return false;
            if (node[next[now][v[i]]] <= 0)return false;
            now = next[now][v[i]];
        }
        int count = node[now];
        for (int i = 0; i < kind; ++i)if (-1 != next[now][i])count -= node[next[now][i]];
        return count;
    }
    void erase(const std::vector<int>&v) {
        int now = 0;
        for (int i = 0; i < (int)v.size(); ++i) {
            now = next[now][v[i]];
            node[now]--;
        }
    }
    // Binary Trie
    std::vector<int>xor_max(const std::vector<int>&v) {
        std::vector<int>ret;
        int now = 0;
        for (int i = 0; i < (int)v.size(); ++i) {
            std::vector<int>tmp = { 1 - v[i],v[i] };
            for (int j = 0; j < (int)tmp.size(); ++j) {
                if (-1 == next[now][tmp[j]])continue;
                if (node[next[now][tmp[j]]] <= 0)continue;
                ret.emplace_back(tmp[j]);
                now = next[now][tmp[j]];
                break;
            }
        }
        return ret;
    }
    std::vector<int>xor_min(const std::vector<int>&v) {
        std::vector<int>ret;
        int now = 0;
        for (int i = 0; i < (int)v.size(); ++i) {
            std::vector<int>tmp = { v[i],1 - v[i] };
            for (int j = 0; j < (int)tmp.size(); ++j) {
                if (-1 == next[now][tmp[j]])continue;
                if (node[next[now][tmp[j]]] <= 0)continue;
                ret.emplace_back(tmp[j]);
                now = next[now][tmp[j]];
                break;
            }
        }
        return ret;
    }
    // xとxorした結果がk未満になる物の数(0含む)
    int xor_count(const std::vector<int>&x, const std::vector<int>&k) {
        int ret = 0, now = 0;
        for (int i = 0; i < (int)k.size(); ++i) {
            if (0 == k[i]) {
                if (-1 == next[now][x[i]])break;
                now = next[now][x[i]];
            }
            else {
                if (-1 != next[now][x[i]])ret += node[next[now][x[i]]];
                if (-1 == next[now][1 - x[i]])break;
                now = next[now][1 - x[i]];
            }
        }
        return ret;
    }
    // xより大きいものの個数
    int over_count(const std::vector<int>&x) {
        int ret = 0, now = 0;
        for (int i = 0; i < (int)x.size(); ++i) {
            if (0 == x[i]) {
                if (-1 != next[now][1])ret += node[next[now][1]];
            }
            if (-1 == next[now][x[i]])break;
            now = next[now][x[i]];
        }
        return ret;
    }
    std::vector<int> trans(long long n, int sz = 30) {
        std::vector<int>ret(sz, 0);
        for (int i = 0; i < sz; ++i) {
            if (1 & (n >> i))ret[sz - 1 - i] = 1;
        }
        return ret;
    }
    long long inverse(const std::vector<int>&v) {
        long long ret = 0;
        for (int i = 0; i < v.size(); ++i) {
            ret *= 2;
            ret += v[i];
        }
        return ret;
    }
};
template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
    while (abs(ok - ng) > 1) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
int main() {
    int n; cin >> n;
    long long k; cin >> k;
    auto trie = BinaryTrie(2);
    vector<int>a(n);
    rep(i, n)cin >> a[i];
    vector<vector<int>>ta(n);
    rep(i, n) {
        trie.insert(trie.trans(a[i]));
        ta[i] = trie.trans(a[i]);
    }
    auto f = [&](const long long x)->bool {
        long long cnt = 0;
        auto vx = trie.trans(x + 1);
        rep(i, n) {
            cnt += trie.xor_count(ta[i], vx) - 1;
        }
        cnt /= 2;
        return k <= cnt;
    };
    auto ans = binarySearch<long long>((1 << 30), -1, f);
    cout << ans << endl;
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0