# Untitled

a guest
Aug 11th, 2016
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct Node {
2.   unique_ptr<Node> children[2];
3.   int count = 0;
4.   int value = -1;
5. };
6.
7. void insert_number(Node *root, const int num, int add) {
8.   for (int i = 31; i >= 0; --i) {
9.     int idx = (bool)(num & (1 << i));
10.     if (!root->children[idx]) {
11.       root->children[idx].reset(new Node());
12.     }
14.     root = root->children[idx].get();
15.   }
17.   root->value = num;
18. }
19.
20. int get_max_xor(Node *root, const int num, int level) {
21.   if (level < 0) {
22.     int v = root->value;
23.     assert(v != -1);
24.     int ret = num ^ v;
25.     return ret;
26.   }
27.   int bit = 1 - (bool)(num & (1 << level));
28.   if (root->children[bit] && root->children[bit]->count > 0) {
29.     return get_max_xor(root->children[bit].get(), num, level - 1);
30.   } else {
31.     return get_max_xor(root->children[1 - bit].get(), num, level - 1);
32.   }
33. }
34.
35. void solve(const int n) {
36.   unique_ptr<Node> root(new Node());
37.   insert_number(root.get(), 0, +1);
38.
39.   for (int i = 0; i < n; ++i) {
40.     char c; cin >> c;
41.     int num; cin >> num;
42.     if (c == '+') {
43.       insert_number(root.get(), num, +1);
44.     } else if (c == '-') {
45.       insert_number(root.get(), num, -1);
46.     } else {
47.       int ret = get_max_xor(root.get(), num, 31);
48.       cout << ret << "\n";
49.     }
50.   }
51.
52.   cout.flush();
53. }