Advertisement
Beingamanforever

maximumxor

Oct 21st, 2024
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. /**
  2.  *    author:  compounding
  3.  *    created: 2024-10-21 17:38:25
  4.  **/
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
  8. #define NeedForSpeed                  \
  9.     ios_base::sync_with_stdio(false); \
  10.     cin.tie(NULL);                    \
  11.     cout.tie(NULL);
  12. #define int long long
  13. #define all(x) (x).begin(), (x).end()
  14. typedef vector<int> vi;
  15. typedef vector<bool> vb;
  16. typedef vector<vi> vvi;
  17. typedef vector<pair<int, int>> vpi;
  18. #define f first
  19. #define s second
  20. #define endl "\n"
  21. const int mod = 1000000007;
  22. int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
  23. struct node
  24. {
  25.     node *links[2] = {nullptr, nullptr};
  26.     bool contains(int bit)
  27.     {
  28.         return links[bit] != nullptr;
  29.     }
  30.     node *get(int bit)
  31.     {
  32.         return links[bit];
  33.     }
  34.     void put(int bit, node *nextnode)
  35.     {
  36.         links[bit] = nextnode;
  37.     }
  38. };
  39.  
  40. class trie
  41. {
  42. private:
  43.     node *root;
  44.  
  45. public:
  46.     trie()
  47.     {
  48.         root = new node();
  49.     }
  50.     void insert(int num)
  51.     {
  52.         node *move = root;
  53.         for (int i = 31; i >= 0; i--)
  54.         {
  55.             int bit = (num >> i) & 1;
  56.             if (!move->contains(bit))
  57.             {
  58.                 move->put(bit, new node());
  59.             }
  60.             move = move->get(bit);
  61.         }
  62.     }
  63.     int getmax(int num)
  64.     {
  65.         node *move = root;
  66.         int maxi = 0;
  67.         for (int i = 31; i >= 0; i--)
  68.         {
  69.             int bit = (num >> i) & 1;
  70.             if (move->contains(!bit))
  71.             {
  72.                 maxi |= (1 << i);
  73.                 move = move->get(!bit);
  74.             }
  75.             else
  76.             {
  77.                 move = move->get(bit);
  78.             }
  79.         }
  80.         return maxi;
  81.     }
  82. };
  83.  
  84. void solve()
  85. {
  86.     int n;
  87.     cin >> n;
  88.     vi v(n);
  89.     int maxixor = 0, prexor = 0;
  90.     trie t;
  91.     t.insert(0);
  92.     for (int i = 0; i < n; i++)
  93.     {
  94.         cin >> v[i];
  95.         prexor ^= v[i];
  96.         maxixor = max(maxixor, t.getmax(prexor));
  97.         t.insert(prexor);
  98.     }
  99.     cout << maxixor << endl;
  100. }
  101.  
  102. signed main()
  103. {
  104.     NeedForSpeed;
  105.     int t = 1;
  106.     cin >> t;
  107.     while (t--)
  108.     {
  109.         solve();
  110.     }
  111.     return 0;
  112. }
  113.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement