Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
33467 | _ | Xor Sum | C++ | 通过 | 100 | 362 MS | 53312 KB | 1299 | 2021-12-06 13:55:55 |
#include <bits/stdc++.h> using namespace std; struct Node { int son[2], sz; Node(): sz(0) { son[0] = son[1] = 0; } }; struct Trie01 { static const int MAXD = 16; vector<Node> nodes; Trie01() { nodes.resize(2); } void add(int x, int val) { int cur(1); nodes[cur].sz += val; for (int i(MAXD); ~i; --i) { int dg(x >> i & 1); if (!nodes[cur].son[dg]) nodes[cur].son[dg] = nodes.size(), nodes.push_back(Node()); cur = nodes[cur].son[dg]; nodes[cur].sz += val; } } int getxor(int x) const { int cur(1), res(0); for (int i(MAXD); ~i; --i) { int dg(x >> i & 1); if (nodes[nodes[cur].son[dg ^ 1]].sz > 0) cur = nodes[cur].son[dg ^ 1], res ^= 1 << i; else cur = nodes[cur].son[dg]; } return res ^ x; } }; int read() { int x(0); char c(getchar()); while (c < '0' || c > '9') c = getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); return x; } int main() { const int T(read()); for (int caseid(1); caseid <= T; ++caseid) { printf("Case #%d:\n", caseid); int N(read()), M(read()); Trie01 trie; for (int x; N--; ) { x = read(); trie.add(x, 1); } for (int x; M--; ) { x = read(); printf("%d\n", trie.getxor(x)); } } return 0; }