fork(11) download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdio>
  4. #include <map>
  5. #include <set>
  6. #include <queue>
  7. #include <stack>
  8. #include <vector>
  9. #include <string>
  10. #include <ctime>
  11. #include <cassert>
  12. #include <algorithm>
  13. #include <cmath>
  14.  
  15. //#include <unordered_set>
  16. //#include <unordered_map>
  17.  
  18. #define forn(i, n) for (int i = 0; i < int(n); i++)
  19. #define for1(i, n) for (int i = 1; i < int(n); i++)
  20. #define forft(i, from, to) for (int i = int(from); i < int(to); i++)
  21. #define forr(i, n) for (int i = int(n) - 1; i >= 0; i--)
  22. #define X first
  23. #define Y second
  24. #define mp make_pair
  25. #define pb push_back
  26. #define sz(a) int(a.size())
  27. #define all(a) a.begin(), a.end()
  28. #define ms(a, v) memset(a, v, sizeof(a))
  29. #define correct(x, y, n, m) (x >= 0 && x < n && y >= 0 && y < m)
  30.  
  31. using namespace std;
  32.  
  33. template<typename T> T sqr(const T &x) {
  34.     return x * x;
  35. }
  36.  
  37. typedef long long ll;
  38. typedef long long li;
  39. typedef pair<int, int> pt;
  40. typedef long double ld;
  41. typedef pair<ld, ld> pd;
  42.  
  43. const int INF = int(1e9);
  44. const ll INF_LL = ll(4e18);
  45. const ll INF64 = ll(4e18);
  46. const ll LINF = ll(4e18);
  47. const ld EPS = 1e-9;
  48. const ld PI = 3.14159265358979323846264338;
  49.  
  50. const int N = 3e5 + 10;
  51. const int M = 20;
  52.  
  53. int n, m;
  54. int a[N];
  55.  
  56. struct node {
  57.     int nxt[2];
  58.     int d;
  59.  
  60.     node() {
  61.         nxt[0] = -1;
  62.         nxt[1] = -1;
  63.         d = 0;
  64.     }
  65. };
  66.  
  67. node t[N * M];
  68. int len = 1;
  69.  
  70. bool read() {
  71.     scanf("%d%d", &n, &m);
  72.  
  73.     forn(i, n) {
  74.         scanf("%d", &a[i]);
  75.     }
  76.  
  77.     return true;
  78. }
  79.  
  80. void add(int v, int num, int pos) {
  81.     if (pos < 0) {
  82.         t[v].d = 1;
  83.         return;
  84.     }
  85.  
  86.     int nxt = ((num >> pos) & 1);
  87.  
  88.     if (t[v].nxt[nxt] == -1) {
  89.         t[v].nxt[nxt] = len++;
  90.     }
  91.  
  92.     add(t[v].nxt[nxt], num, pos - 1);
  93.     t[v].d = 0;
  94.  
  95.     if (t[v].nxt[0] != -1) {
  96.         t[v].d += t[t[v].nxt[0]].d;
  97.     }
  98.  
  99.     if (t[v].nxt[1] != -1) {
  100.         t[v].d += t[t[v].nxt[1]].d;
  101.     }
  102. }
  103.  
  104. void get(int v, int num, int pos, int &ans) {
  105.     if (v == -1) {
  106.         return;
  107.     }
  108.  
  109.     int nxt = ((num >> pos) & 1);
  110.  
  111.     if (t[t[v].nxt[nxt]].d == (1 << pos)) {        
  112.         nxt = 1 - nxt;
  113.     }
  114.  
  115.     ans |= ((nxt ^ ((num >> pos) & 1)) << pos);
  116.     get(t[v].nxt[nxt], num, pos - 1, ans);
  117. }
  118.  
  119. void solve() {
  120.     forn(i, n) {
  121.         add(0, a[i], M - 1);
  122.     }
  123.  
  124.     int c = 0;
  125.  
  126.     forn(i, m) {
  127.         int k;
  128.         scanf("%d", &k);
  129.         c ^= k;
  130.  
  131.         int ans = 0;
  132.         get(0, c, M - 1, ans);
  133.         printf("%d\n", ans);
  134.     }
  135. }
  136.  
  137. int main() {
  138.     srand((int) time(NULL));
  139.     cout << setprecision(10) << fixed;
  140.  
  141.     read();
  142.     solve();
  143.  
  144.     cerr << clock() << endl;
  145.  
  146.     return 0;
  147. }
Success #stdin #stdout #stderr 0.03s 86720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
32302
https://ideone.com/gVE1kC
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!