Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
33423 | wzj33300 | Xor Sum | C++ | 运行出错 | 0 | 0 MS | 240 KB | 1466 | 2021-12-06 13:39:53 |
#include <bits/stdc++.h> using namespace std; struct node { int son[2]; int vis, num; node(int son1 = 0, int son2 = 0, int vis = 0, int num = 0) : son {son1, son2}, vis(vis), num(num) {} }; vector<node> t(1); #define int long long inline int read() { int x=0; char c=getchar(); for(; c<'0' || c>'9'; c=getchar()); for(; c<='9' && c>='0'; c=getchar()) x=(x<<3)+(x<<1)+c-'0'; return x; } void add(int x) { t[0].vis++; int p = 0; for (int i = 63; i >= 0; i--) { bool wz = (x >> i) & 1; if (!t[p].son[wz]) t.push_back({}), t[p].son[wz] = t.size() - 1; p = t[p].son[wz]; t[p].vis++; } t[p].num = x; } void del(int x) { t[0].vis--; int p = 0; for (int i = 63; i >= 0; i--) { bool wz = (x >> i) & 1; p = t[p].son[wz]; if (p) t[p].vis--; } } int solve(int x) { int p = 0; for (int i = 63; i >= 0; i--) { bool wz = (x >> i) & 1; if (t[p].son[!wz] && t[t[p].son[!wz]].vis) p = t[p].son[!wz]; else p = t[p].son[wz]; } return t[p].num; } int qq, q, n, m, a[100005]; signed main() { freopen("xor.in","r",stdin); freopen("xor.out","w",stdout); q = read(); while (q--) { printf("Case #%d:\n", ++qq); int ans = -1; t.assign(1, {0,0,0,0}); n = read(), m = read(); for (int i = 1; i <= n; i++) { a[i] = read(); add(a[i]); } for (int kkk, i = 1; i <= m; i++) { kkk = read(); printf("%lld\n", solve(kkk)); } } return 0; }