Advertisement
Guest User

Untitled

a guest
Aug 11th, 2016
186
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  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.     }
  13.     root->count += add;
  14.     root = root->children[idx].get();
  15.   }
  16.   root->count += add;
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement