好题。
套路地，考虑枚举最优解的 \(a\) 异或和二进制下与 \(k\) 的 \(\text{LCP}\)，设在第 \(i\) 位不同。这样的好处是 \(i\) 之后的位可以随便选。
之后按位贪心确定最优解 \(b\) 的异或和。考虑之前的答案是 \(res\)，当前在确定第 \(j\) 位，如何判断 \(res + 2^j\) 可行。
考虑将 \(2^i \left\lfloor\frac{a}{2^i}\right\rfloor\) 和 \(2^j \left\lfloor\frac{b}{2^j}\right\rfloor\) 拼成一个 \(60\) 位的二进制数，把它插入线性基内，判断 \(res + 2^j\) 能否被这些数凑出来即可。
注意最后要检查 \(res\) 是否能被 \(b_i\) 凑出来。
code
// Problem: G - Xor Cards
// Contest: AtCoder - Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）
// URL: https://atcoder.jp/contests/abc249/tasks/abc249_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
struct LinearBasis {
ll p[65];
bool fl;
inline void init() {
fl = 0;
mems(p, 0);
}
inline void insert(ll x) {
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i]) {
p[i] = x;
return;
}
x ^= p[i];
}
}
fl = 1;
}
inline bool check(ll x) {
if (!x) {
return fl;
}
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i]) {
return 0;
}
x ^= p[i];
}
}
return 1;
}
} B;
const int maxn = 1010;
ll n, m, a[maxn], b[maxn];
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld%lld", &a[i], &b[i]);
}
ll ans = -1;
for (int i = 29; i >= -1; --i) {
if (i >= 0 && ((~m) & (1LL << i))) {
continue;
}
ll k = (i == -1 ? m : (((m ^ (1LL << i)) >> i) << i)), res = 0;
for (int j = 29; ~j; --j) {
B.init();
for (int k = 1; k <= n; ++k) {
B.insert((((a[k] >> max(0, i)) << max(0, i)) << 30) | ((b[k] >> j) << j));
}
if (B.check((k << 30) | (res | (1LL << j)))) {
res |= (1LL << j);
}
}
B.init();
for (int k = 1; k <= n; ++k) {
B.insert((((a[k] >> max(0, i)) << max(0, i)) << 30) | b[k]);
}
if (B.check((k << 30) | res)) {
ans = max(ans, res);
}
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}