Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <array>
- #include <vector>
- #include <numeric>
- #include <random>
- #include <chrono>
- #include <set>
- #include <cassert>
- #include <bitset>
- using namespace std;
- #define int long long
- #pragma comment(linker,"/STACK:1000000000,1000000000")
- const long long INF = 1e9 + 7;
- const int MAXN = 2e5 * 32 + 100;
- const int N = 1e5 + 10;
- struct vertex {
- int next[3];
- int terminal = 0;
- } v[MAXN];
- array<int, MAXN> kol;
- int root = 0, top = 1;
- inline void add(int num) {
- int cur = root;
- bitset<32> a(num);
- for (int i = 31; i >= 0; --i) {
- if (v[cur].next[a[i]] == 0) {
- v[cur].next[a[i]] = top++;
- }
- ++kol[cur];
- cur = v[cur].next[a[i]];
- }
- ++kol[cur];
- v[cur].terminal = num;
- }
- inline void del(int num) {
- int cur = root;
- bitset<32> a(num);
- for (int i = 31; i >= 0; --i) {
- --kol[cur];
- cur = v[cur].next[a[i]];
- }
- --kol[cur];
- v[cur].terminal = 0;
- }
- inline int get(int num) {
- int cur = root;
- bitset<32> a(num);
- int res = 0;
- for (int i = 31; i >= 0; --i) {
- if (v[cur].next[!a[i]] != 0 && kol[v[cur].next[!a[i]]]) {
- cur = v[cur].next[!a[i]];
- res |= 1 << i;
- } else {
- cur = v[cur].next[a[i]];
- }
- }
- return res;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- add(0);
- int q;
- cin >> q;
- while (q--) {
- char type;
- int x;
- cin >> type >> x;
- if (type == '+') {
- add(x);
- } else if (type == '-') {
- del(x);
- } else if (type == '?') {
- cout << get(x) << '\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment