結果
| 問題 | No.2977 Kth Xor Pair |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-10-22 21:21:14 |
| 言語 | C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 6,125 bytes |
| 記録 | |
| コンパイル時間 | 2,232 ms |
| コンパイル使用メモリ | 343,080 KB |
| 実行使用メモリ | 48,408 KB |
| 最終ジャッジ日時 | 2026-10-22 21:22:25 |
| 合計ジャッジ時間 | 52,711 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 35 WA * 1 |
ソースコード
#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>
/**
* @file binary_trie.hpp
* @brief Binary Trie
* @author kwm_t
* @see https://github.com/kwm-t/cp-library/blob/main/datastructure/binary_trie.hpp
*/
#ifndef KWM_T_DATA_STRUCTURE_BINARY_TRIE_HPP
#define KWM_T_DATA_STRUCTURE_BINARY_TRIE_HPP
#include <array>
#include <vector>
#include <type_traits>
/**
* @brief Binary Trie（XOR系クエリ対応Trie）
*
* 整数を2進表現として管理するTrie
*
* 典型用途:
* - xor最大/最小
* - k番目の値
* - xor制約付きカウント
*
* 計算量:
* - 各操作 O(bit)
*
* @tparam T int / long long を想定
*
* 制約 / 注意:
* - eraseは存在する値にのみ使用すること
* - bit長はコンストラクタで調整可能
*
* verified:
* - https://atcoder.jp/contests/abc451/submissions/74523720
*/
namespace kwm_t::data_structure {
template<class T = int>
struct BinaryTrie {
private:
static constexpr int default_bit() {
if constexpr (std::is_same_v<T, int>) return 30;
else return 60;
}
int bit;
std::vector<int> node;
std::vector<std::array<int, 2>> next;
const std::array<int, 2> e{ -1, -1 };
std::vector<int> trans(T x) const {
std::vector<int> ret(bit, 0);
for (int i = 0; i < bit; ++i) {
if ((x >> i) & 1) ret[bit - 1 - i] = 1;
}
return ret;
}
T inverse(const std::vector<int>& v) const {
T ret = 0;
for (int i = 0; i < (int)v.size(); ++i) {
ret = (ret << 1) | v[i];
}
return ret;
}
public:
BinaryTrie(int _bit = default_bit())
: bit(_bit) {
node.resize(1);
next.emplace_back(e);
}
static int calc_bit(T max_val) {
int b = 0;
while ((T(1) << b) <= max_val) b++;
return b;
}
void insert(const std::vector<int>& v) {
int now = 0;
for (int i = 0; i < bit; ++i) {
if (next[now][v[i]] == -1) {
next[now][v[i]] = node.size();
node.emplace_back(0);
next.emplace_back(e);
}
now = next[now][v[i]];
node[now]++;
}
}
void insert(T x) { insert(trans(x)); }
void erase(const std::vector<int>& v) {
int now = 0;
for (int i = 0; i < bit; ++i) {
now = next[now][v[i]];
node[now]--;
}
}
void erase(T x) { erase(trans(x)); }
bool search(const std::vector<int>& v) const {
int now = 0;
for (int i = 0; i < bit; ++i) {
if (next[now][v[i]] == -1) return false;
if (node[next[now][v[i]]] <= 0) return false;
now = next[now][v[i]];
}
int cnt = node[now];
for (int i = 0; i < 2; ++i) {
if (next[now][i] != -1) cnt -= node[next[now][i]];
}
return cnt > 0;
}
bool search(T x) const { return search(trans(x)); }
vector<int> kth_element_vec(int k) const {
int now = 0;
std::vector<int> v;
while (true) {
bool ok = false;
for (int i = 0; i < 2; ++i) {
if (next[now][i] == -1) continue;
if (k <= node[next[now][i]]) {
v.push_back(i);
now = next[now][i];
ok = true;
break;
}
else {
k -= node[next[now][i]];
}
}
if (!ok) break;
}
return v;
}
T kth_element(int k) const { return inverse(kth_element_vec(k)); }
std::vector<int> xor_max(const std::vector<int>& v) const {
std::vector<int> ret;
int now = 0;
for (int i = 0; i < bit; ++i) {
int want[2] = { 1 - v[i], v[i] };
for (int t : want) {
if (next[now][t] == -1) continue;
if (node[next[now][t]] <= 0) continue;
ret.push_back(t);
now = next[now][t];
break;
}
}
return ret;
}
T xor_max(T x) const { return inverse(xor_max(trans(x))); }
std::vector<int> xor_min(const std::vector<int>& v) const {
std::vector<int> ret;
int now = 0;
for (int i = 0; i < bit; ++i) {
int want[2] = { v[i], 1 - v[i] };
for (int t : want) {
if (next[now][t] == -1) continue;
if (node[next[now][t]] <= 0) continue;
ret.push_back(t);
now = next[now][t];
break;
}
}
return ret;
}
T xor_min(T x) const { return inverse(xor_min(trans(x))); }
int xor_count(const std::vector<int>& vx, const std::vector<int>& vk) const {
int ret = 0, now = 0;
for (int i = 0; i < bit; ++i) {
if (vk[i] == 0) {
if (next[now][vx[i]] == -1) break;
now = next[now][vx[i]];
}
else {
if (next[now][vx[i]] != -1)
ret += node[next[now][vx[i]]];
if (next[now][1 - vx[i]] == -1) break;
now = next[now][1 - vx[i]];
}
}
return ret;
}
int xor_count(T x, T k) const { return xor_count(trans(x), trans(k)); }
int over_count(const std::vector<int>& v) const {
int ret = 0, now = 0;
for (int i = 0; i < bit; ++i) {
if (v[i] == 0) {
if (next[now][1] != -1)
ret += node[next[now][1]];
}
if (next[now][v[i]] == -1) break;
now = next[now][v[i]];
}
return ret;
}
int over_count(T x) const { return over_count(trans(x)); }
int size() const { return node[0]; }
};
} // namespace kwm_t::data_structure
#endif // KWM_T_DATA_STRUCTURE_BINARY_TRIE_HPP
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;
kwm_t::data_structure::BinaryTrie<int> trie;
vector<int>a(n);
rep(i, n)cin >> a[i];
rep(i, n) {
trie.insert(a[i]);
}
auto f = [&](const long long x)->bool {
long long cnt = 0;
rep(i, n) {
cnt += trie.xor_count(a[i], x + 1) - 1;
}
cnt /= 2;
return k <= cnt;
};
auto ans = binarySearch<long long>((1 << 30), -1, f);
cout << ans << endl;
return 0;
}