Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset - dblank

# Codeforces Round #367 (Div. 2) D. Vasiliy's Multiset


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#define endl '\n'
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
int num[50];
struct node
{
int data;
node *nxt[2];
node()
{
data = 0;
memset(nxt, 0, sizeof(nxt));
}
};
node * root = new node;
int *change(int x)
{
for(int i = 0; i<=30; i++)
{
num[30 - i] = x & 1;
x>>=1;
}
return num;
}
void insert_tree(int *num, int mark)
{
node * p = root;
for(int i = 0; i<=30; i++)
{
if(p->nxt[num[i]] == NULL)
{
p->nxt[num[i]] = new node;
}
p = p->nxt[num[i]];
p->data += mark;
}
}
int query(int *num)
{
int res = 0;
node *p = root;
for(int i = 0; i<=30; i++)
{
int id = -1, ok = 0;
for(int j = 0; j<=1; j++)
{

if(num[i] ^ j == 1 && p->nxt[j]!=NULL &&p->nxt[j]->data != 0)
{
id = j;
}
if(p->nxt[j]!=NULL &&p->nxt[j]->data != 0)
ok = 1;
}
if(id !=-1)
res |= 1<< 30- i;
else if(id == -1)
id = num[i];
if(!ok)
return -1;
p = p->nxt[id];
}
return res;
}
int main()
{
int n;
while(cin>>n)
{
char c;
int x;
for(int i = 0; i<n; i++)
{
scanf(" %c%d", &c, &x);
if(c == '+')
insert_tree(change(x), 1);
if(c == '-')
insert_tree(change(x), -1);
if(c == '?')
{
int ans = query(change(x));
if(ans == -1)
printf("%d\n", x);
else printf("%d\n", max(ans, x));
}
}
}
return 0;