結果
| 問題 |
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 |
ソースコード
#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';
}