Advertisement
PikMike

Untitled

Aug 11th, 2016
338
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define sz size
  6. #define ll long long
  7. #define ld long double
  8. #define fs first
  9. #define sc second
  10. #define forn(i, f, t) for(int i = f; i < t; i++)
  11. #define all(x) (x).begin(), (x).end()
  12. #define ins insert
  13.  
  14. const int INF = 2147483647;
  15. const int MOD = 1000000007;
  16. const ll INF64 = 9223372036854775807;
  17. const ld EPS = 1e-7;
  18.  
  19. using namespace std;
  20.  
  21. struct node{
  22.     int next[2];
  23.     int isFinal;
  24. } ar[1000001];
  25.  
  26. int cnt = 0;
  27.  
  28. void add(int x){
  29.     int cur = 0;
  30.     for (int i = 30; i >= 0; i--)
  31.         if (ar[cur].next[x & (1 << i) ? 1 : 0] != -1){
  32.             cur = ar[cur].next[x & (1 << i) ? 1 : 0];
  33.             ar[cur].isFinal++;
  34.         }
  35.         else{
  36.             ar[cur].next[x & (1 << i) ? 1 : 0] = ++cnt;
  37.             cur = ar[cur].next[x & (1 << i) ? 1 : 0];
  38.             ar[cur].isFinal = 1;
  39.             ar[cur].next[0] = ar[cur].next[1] = -1;
  40.         }
  41. }
  42.  
  43.  
  44. void rem(int x){
  45.     int cur = 0;
  46.     for (int i = 30; i >= 0; i--){
  47.         cur = ar[cur].next[x & (1 << i) ? 1 : 0];
  48.         ar[cur].isFinal--;
  49.     }
  50. }
  51.  
  52.  
  53. int find(int x){
  54.     int cur = 0, tmp = 0;
  55.     for (int i = 30; i >= 0; i--)
  56.         if (ar[cur].next[x & (1 << i) ? 0 : 1] != -1 && ar[ar[cur].next[x & (1 << i) ? 0 : 1]].isFinal){
  57.             tmp += (1 << i);
  58.             cur = ar[cur].next[x & (1 << i) ? 0 : 1];
  59.         }
  60.         else
  61.             cur = ar[cur].next[x & (1 << i) ? 1 : 0];
  62.     return tmp;
  63. }
  64.  
  65.  
  66. int main(){
  67.     int n, x;
  68.     scanf("%d", &n);
  69.     char c;
  70.     ar[0].next[0] = -1;
  71.     ar[0].next[1] = -1;
  72.     ar[0].isFinal = 0;
  73.     forn(i, 0, n){
  74.         scanf("\n%c %d", &c, &x);
  75.         if (c == '+') add(x);
  76.         else if (c == '-') rem(x);
  77.         else if (c == '?') printf("%d\n", find(x));
  78.     }
  79.  
  80.     return 0;
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement