Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct Node {
- unique_ptr<Node> children[2];
- int count = 0;
- int value = -1;
- };
- void insert_number(Node *root, const int num, int add) {
- for (int i = 31; i >= 0; --i) {
- int idx = (bool)(num & (1 << i));
- if (!root->children[idx]) {
- root->children[idx].reset(new Node());
- }
- root->count += add;
- root = root->children[idx].get();
- }
- root->count += add;
- root->value = num;
- }
- int get_max_xor(Node *root, const int num, int level) {
- if (level < 0) {
- int v = root->value;
- assert(v != -1);
- int ret = num ^ v;
- return ret;
- }
- int bit = 1 - (bool)(num & (1 << level));
- if (root->children[bit] && root->children[bit]->count > 0) {
- return get_max_xor(root->children[bit].get(), num, level - 1);
- } else {
- return get_max_xor(root->children[1 - bit].get(), num, level - 1);
- }
- }
- void solve(const int n) {
- unique_ptr<Node> root(new Node());
- insert_number(root.get(), 0, +1);
- for (int i = 0; i < n; ++i) {
- char c; cin >> c;
- int num; cin >> num;
- if (c == '+') {
- insert_number(root.get(), num, +1);
- } else if (c == '-') {
- insert_number(root.get(), num, -1);
- } else {
- int ret = get_max_xor(root.get(), num, 31);
- cout << ret << "\n";
- }
- }
- cout.flush();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement