Advertisement
MathQ_

Untitled

Mar 8th, 2021
131
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. const int MAX = 2e5 * 32;
  2. vector<node> t(MAX);
  3. int leaf = 1;
  4.  
  5. string bin(int &num) {
  6.     string res;
  7.     while (num) {
  8.         res += '0' + (num & 1);
  9.         num >>= 1;
  10.     }
  11.     reverse(all(res));
  12.     int k = 30 - res.size();
  13.     string zeroes;
  14.     for (int i = 0; i < k; ++i) zeroes += '0';
  15.     return zeroes + res;
  16. }
  17.  
  18. int unbin(string &num) {
  19.     int res = 0; int deg = (1 << (int)(num.size()) - 1);
  20.     for (auto el : num) {
  21.         int k = el - '0';
  22.         res += k * deg;
  23.         deg >>= 1;
  24.     }
  25.     return res;
  26. }
  27.  
  28. void add(int &num) {
  29.     int v = 0;
  30.     string bin_num = bin(num);
  31.     for (auto el : bin_num) {
  32.         int k = el - '0';
  33.         if (t[v].next[k] == 0) {
  34.             t[v].next[k] = leaf++;
  35.         }        
  36.         v = t[v].next[k]; t[v].cnt++;
  37.     }
  38. }
  39.  
  40. void del(int &num) {
  41.     int v = 0;
  42.     string bin_num = bin(num);
  43.     for (auto el : bin_num) {
  44.         v = t[v].next[el - '0'];
  45.         t[v].cnt--;
  46.     }
  47. }
  48.  
  49. void get(int &num) {
  50.     int v = 0;
  51.     int num1 = num;
  52.     string bin_num = bin(num1);
  53.     string ans;
  54.     for (auto el : bin_num) {
  55.         int k = el - '0';
  56.         if (t[t[v].next[1 - k]].cnt) {
  57.             v = t[v].next[1 - k];
  58.             ans += (1 - k) + '0';
  59.         } else {
  60.             v = t[v].next[k];
  61.             ans += el;
  62.         }
  63.     }
  64.     cout << (unbin(ans) ^ num) << '\n';
  65. }
  66.  
  67. int main() {
  68.     int q;
  69.     cin >> q;
  70.     char type; int x;
  71.     while (q--) {
  72.         cin >> type >> x;
  73.         if (type == '+') {
  74.             add(x);
  75.         } else if (type == '-') {
  76.             del(x);
  77.         } else {
  78.             get(x);
  79.         }
  80.     }
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement