Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
33467 _ Xor Sum C++ 通过 100 362 MS 53312 KB 1299 2021-12-06 13:55:55

Tests(10/10):


#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; }


测评信息: