結果
問題 | No.2977 Kth Xor Pair |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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,falseif (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';}