結果

問題 No.2977 Kth Xor Pair
ユーザー coindarw
提出日時 2024-12-03 03:48:45
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,819 ms / 3,000 ms
コード長 12,492 bytes
コンパイル時間 2,800 ms
コンパイル使用メモリ 250,412 KB
実行使用メモリ 53,368 KB
最終ジャッジ日時 2024-12-03 03:49:35
合計ジャッジ時間 38,789 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using ll = long long;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
constexpr int inf = 2000'000'000;
constexpr ll linf = 4000000000000000000ll;
constexpr ll M7 = 1000000007ll;
constexpr ll M09 = 1000000009ll;
constexpr ll M9 = 998244353ll;
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;

template <int B, typename T = uint32_t>
class BinaryTrie {
   public:
    struct Node {
        int next[2];
        int common;
        Node() : common(0) { next[0] = next[1] = -1; }
    };

   private:
    T lazy;
    vector<Node> _nodes;

   public:
    BinaryTrie() : lazy(T(0)) { _nodes = vector<Node>(1, Node()); }
    void insert(const T &x) {
        int node_id = 0;
        for (int i = 0; i < B; ++i) {
            int c = ((x ^ lazy) >> (B - i - 1)) & 1;
            if (_nodes[node_id].next[c] == -1) {
                _nodes[node_id].next[c] = int(_nodes.size());
                _nodes.push_back(Node());
            }
            ++_nodes[node_id].common;
            node_id = _nodes[node_id].next[c];
        }
        ++_nodes[node_id].common;
    }
    void erase(const T &x) {
        int node_id = 0;
        --_nodes[node_id].common;
        for (int i = 0; i < B; ++i) {
            int c = ((x ^ lazy) >> (B - i - 1)) & 1;
            assert(_nodes[node_id].next[c] != -1);
            node_id = _nodes[node_id].next[c];
            --_nodes[node_id].common;
        }
    }
    int size() const { return _nodes[0].common; }
    bool empty() const { return size() == 0; }
    void clear() {
        _nodes = vector<Node>(1, Node(0));
        lazy = T(0);
    }

    T min_element() const {
        assert(!empty());
        int node_id = 0;
        T ret = 0;
        for (int i = 0; i < B; ++i) {
            int lz = lazy >> (B - i - 1) & 1;
            int nxt = lz;
            if (_nodes[node_id].next[nxt] == -1 || _nodes[_nodes[node_id].next[nxt]].common == 0) nxt ^= 1;
            int next_node_id = _nodes[node_id].next[nxt];
            ret |= (T(nxt ^ lz) << (B - i - 1));
            node_id = next_node_id;
        }
        return ret;
    }
    T max_element() const {
        assert(!empty());
        int node_id = 0;
        T ret = 0;
        for (int i = 0; i < B; ++i) {
            int lz = lazy >> (B - i - 1) & 1;
            int nxt = lz ^ 1;
            if (_nodes[node_id].next[nxt] == -1 || _nodes[_nodes[node_id].next[nxt]].common == 0) nxt ^= 1;
            int next_node_id = _nodes[node_id].next[nxt];
            ret |= (T(nxt ^ lz) << (B - i - 1));
            node_id = next_node_id;
        }
        return ret;
    }
    int search_id(const T &x) {
        int node_id = 0;
        for (int i = 0; i < B; ++i) {
            int c = ((x ^ lazy) >> (B - i - 1)) & 1;
            int next_id = _nodes[node_id].next[c];
            if (next_id == -1) return -1;
            node_id = next_id;
        }
        return node_id;
    }
    bool contains(const T &x) {
        int node_id = search_id(x);
        return node_id != -1 && _nodes[node_id].common > 0;
    }
    int count(const T &x) {
        int node_id = search_id(x);
        return node_id == -1 ? 0 : _nodes[node_id].common;
    }
    T operator[](int k) {  // k番目のノードの文字列を返す
        assert(0 <= k && k < size());
        int node_id = 0;
        T res = 0;
        for (int i = 0; i < B; ++i) {
            int lz = lazy >> (B - i - 1) & 1;
            int left = lz, right = lz ^ 1;
            if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > k) {
                node_id = _nodes[node_id].next[left];
            } else {
                if (_nodes[node_id].next[left] != -1) k -= _nodes[_nodes[node_id].next[left]].common;
                node_id = _nodes[node_id].next[right];
                res |= (T(1) << (B - i - 1));
            }
        }
        return res;
    }
    void apply_xor(const T &x) { lazy ^= x; }
    const vector<Node> &nodes() { return _nodes; }
    vector<T> dump() {
        vector<T> ret;
        auto f = [&](auto f, int i, int node_id, T x) -> void {
            if (i == B) {
                for (int j = 0; j < _nodes[node_id].common; ++j) ret.push_back(x);
                return;
            }
            int lz = lazy >> (B - i - 1) & 1;
            int left = _nodes[node_id].next[lz];
            int right = _nodes[node_id].next[lz ^ 1];
            if (left != -1 && _nodes[left].common > 0) f(f, i + 1, left, x << 1);
            if (right != -1 && _nodes[right].common > 0) f(f, i + 1, right, (x << 1) | 1);
        };
        f(f, 0, 0, 0);
        return ret;
    }

    template <bool strict>
    pair<T, bool> greater_min_sub(const T &x, int node_id, int i, T y, bool equal) const {  // xより真に大きい/以上の値の中で最小のものの値, 存在しなければ0,false
        if (i == B) {
            if constexpr (strict) return equal ? make_pair(T(0), false) : make_pair(y, true);
            else return make_pair(y, true);
        }
        int b = (x >> (B - i - 1)) & 1;  // xのi桁目
        int lz = lazy >> (B - i - 1) & 1;
        int left = lz, right = lz ^ 1;
        if (equal) {  // まだ上の桁がxと一致しているので、小さい方に存在するならそちらを選び、ないなら大きい方
            if (b == 0 && _nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) {
                auto [res, ok] = greater_min_sub<strict>(x, _nodes[node_id].next[left], i + 1, y << 1, true);
                if (ok) return {res, true};
            }
            if (_nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) {
                auto [res, ok] = greater_min_sub<strict>(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, b == 1);
                if (ok) return {res, true};
            }
        } else {  // 既に大きいことが確定しているので、0を優先して選ぶ
            if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) {
                auto [res, ok] = greater_min_sub<strict>(x, _nodes[node_id].next[left], i + 1, y << 1, false);
                if (ok) return {res, true};
            }
            if (_nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) {
                auto [res, ok] = greater_min_sub<strict>(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, false);
                if (ok) return {res, true};
            }
        }
        return {0, false};
    }
    pair<T, bool> gt_min(const T &x) const {  // xより真に大きい値の中で最小のものの値
        return greater_min_sub<true>(x, 0, 0, 0, true);
    }
    pair<T, bool> geq_min(const T &x) const {  // x以上の値の中で最小のものの値
        return greater_min_sub<false>(x, 0, 0, 0, true);
    }
    template <bool strict>
    pair<T, bool> less_max_sub(const T &x, int node_id, int i, T y, bool equal) const {
        if (i == B) {
            if constexpr (strict) return equal ? make_pair(T(0), false) : make_pair(y, true);
            else return make_pair(y, true);
        }
        int b = (x >> (B - i - 1)) & 1;  // xのi桁目
        int lz = lazy >> (B - i - 1) & 1;
        int left = lz, right = lz ^ 1;
        if (equal) {  // まだ上の桁がxと一致しているので、大きい方に存在するならそちらを選び、ないなら小さい方
            if (b == 1 && _nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) {
                auto [res, ok] = less_max_sub<strict>(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, true);
                if (ok) return {res, true};
            }
            if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) {
                auto [res, ok] = less_max_sub<strict>(x, _nodes[node_id].next[left], i + 1, y << 1, b == 0);
                if (ok) return {res, true};
            }
        } else {  // 既に小さいことが確定しているので、1を優先して選ぶ
            if (_nodes[node_id].next[right] != -1 && _nodes[_nodes[node_id].next[right]].common > 0) {
                auto [res, ok] = less_max_sub<strict>(x, _nodes[node_id].next[right], i + 1, (y << 1) | 1, false);
                if (ok) return {res, true};
            }
            if (_nodes[node_id].next[left] != -1 && _nodes[_nodes[node_id].next[left]].common > 0) {
                auto [res, ok] = less_max_sub<strict>(x, _nodes[node_id].next[left], i + 1, y << 1, false);
                if (ok) return {res, true};
            }
        }
        return {0, false};
    }
    pair<T, bool> lt_max(const T &x) const {  // xより真に小さい値の中で最大のものの値
        return less_max_sub<true>(x, 0, 0, 0, true);
    }
    pair<T, bool> leq_max(const T &x) const {  // x以下の値の中で最大のものの値
        return less_max_sub<false>(x, 0, 0, 0, true);
    }

    template <bool strict>
    int count_less(const T &x) const {  // x未満の値の個数
        if (empty()) return 0;
        int node_id = 0;
        int ret = 0;
        for (int i = 0; i < B; ++i) {
            int b = (x >> (B - i - 1)) & 1;
            int lz = lazy >> (B - i - 1) & 1;
            int left = lz, right = lz ^ 1;
            if (b == 0) {  // xのi桁目が0のとき
                if (_nodes[node_id].next[left] == -1) break;
                node_id = _nodes[node_id].next[left];
            } else {
                if (_nodes[node_id].next[left] != -1) ret += _nodes[_nodes[node_id].next[left]].common;
                if (_nodes[node_id].next[right] == -1) break;
                node_id = _nodes[node_id].next[right];
            }
        }
        if constexpr (!strict) {
            if (_nodes[node_id].next[0] == -1 && _nodes[node_id].next[1] == -1) {  // 子が存在しない=そのノードがx丁度
                ret += _nodes[node_id].common;
            }
        }
        return ret;
    }
    template <bool strict>
    int count_greater(const T &x) const {  // xより大きい値の個数
        if (empty()) return 0;
        int node_id = 0;
        int ret = 0;
        for (int i = 0; i < B; ++i) {
            int b = (x >> (B - i - 1)) & 1;
            int lz = lazy >> (B - i - 1) & 1;
            int left = lz, right = lz ^ 1;
            if (b == 1) {  // xのi桁目が1のとき
                if (_nodes[node_id].next[right] == -1) break;
                node_id = _nodes[node_id].next[right];
            } else {
                if (_nodes[node_id].next[right] != -1) ret += _nodes[_nodes[node_id].next[right]].common;
                if (_nodes[node_id].next[left] == -1) break;
                node_id = _nodes[node_id].next[left];
            }
        }
        if constexpr (!strict) {
            if (_nodes[node_id].next[0] == -1 && _nodes[node_id].next[1] == -1) {  // 子が存在しない=そのノードがx丁度
                ret += _nodes[node_id].common;
            }
        }
        return ret;
    }

    int cout_lt(const T &x) const { return count_less<true>(x); }
    int count_leq(const T &x) const { return count_less<false>(x); }
    int count_gt(const T &x) const { return count_greater<true>(x); }
    int count_geq(const T &x) const { return count_greater<false>(x); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    ll k;
    cin >> n >> k;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    auto bsearch = [&](auto cmp, ll ok, ll ng) {
        while (abs(ng - ok) > 1) {
            ll mid = (ng + ok) / 2;
            if (cmp(mid)) ok = mid;
            else ng = mid;
        }
        return ok;
    };
    BinaryTrie<30> trie;
    rep(i, n) trie.insert(a[i]);
    auto cmp = [&](ll x) -> bool {
        ll cnt = 0;
        rep(i, n) {
            trie.apply_xor(a[i]);
            cnt += trie.count_leq(x) - 1;
            trie.apply_xor(a[i]);
        }
        cnt /= 2;
        return cnt >= k;
    };

    int ans = bsearch(cmp, (1ll << 30) - 1, -1);
    cout << ans << '\n';
}
0