Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.9 kB
0
Indexable
Never
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;


struct Node{
    int cnt;
    int go[2];
    
    Node(){
        cnt=0;
        for (int i = 0; i < 2; i++){
            go[i] = -1;
        }
    }
};

vector<Node> trie;

void addNumber(long long int x){
    int v = 0;
    for (int i = 3; i>-1; i--){
        int cur = ((x >> i) & 1);
        if (trie[v].go[cur] == -1){
            trie.push_back(Node());
            trie[v].go[cur] = trie.size()-1;
        }
        v = trie[v].go[cur];
    }
    trie[v].cnt++;
}

void del(long long int x){
    int v=0;
    for (int i = 3; i>-1; i--){
        int cur = ((x >> i) & 1);
        v = trie[v].go[cur];
    }
    trie[v].cnt--;
}

long long int max_xor(long long int x){
    vector<int> binary;
    int v = 0;
    for (int i = 3; i > -1; i--){
        int cur = ((x >> i) & 1);
        if (cur){
            if (trie[v].go[0]!=-1){
                v = trie[v].go[0];
                binary.push_back(1);
            } else {
                v = trie[v].go[1];
                binary.push_back(0);
            }
        } else {
            int p = trie[v].go[0];
            int pp = trie[v].go[1];
            if (trie[v].go[1]!=-1){
                v = trie[v].go[1];
                binary.push_back(1);
            } else {
                v = trie[v].go[0];
                binary.push_back(0);
            }
        }
    }
    long long int res=0;
    for (int i=0;i<binary.size();i++){
        if (binary[i]) res+=pow(2,binary.size()-1-i);
    }
    return res;
}

int main() {
    trie.push_back(Node());
    long long int q,x,res;
    string s;
    cin>>q;
    for (int i=0;i<q;i++){
        cin>>s>>x;
        if (s == "+"){
            addNumber(x);
        } else if (s == "-"){
            del(x);
        } else {
            res = max_xor(x);
            cout<<res<<endl;
        }
    }
    return 0;
}