TheAnshul

XOR Sum

Sep 27th, 2018
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.92 KB | None | 0 0
  1. /***** TheAnshul *****/
  2.  
  3. #include<bits/stdc++.h>
  4. #define ll          long long
  5. #define pb          push_back
  6. #define ppb         pop_back
  7. #define endl        '\n'
  8. #define mii         map<ll int,ll int>
  9. #define msi         map<string,ll int>
  10. #define mis         map<ll int, string>
  11. #define rep(i,a,b)    for(ll int i=a;i<b;i++)
  12. #define mpi         map<pair<ll int,ll int>,ll int>
  13. #define pii         pair<ll int,ll int>
  14. #define vi          vector<ll int>
  15. #define vii         vector<pair<ll int, ll int>>
  16. #define vs          vector<string>
  17. #define all(a)      (a).begin(),(a).end()
  18. #define F           first
  19. #define S           second
  20. #define sz(x)       (ll int)x.size()
  21. #define hell        1000000007
  22. #define lbnd        lower_bound
  23. #define ubnd        upper_bound
  24. #define bs          binary_search
  25. #define mp          make_pair
  26. #define what_is(x)  cerr << #x << " is " << x << endl;
  27. using namespace std;
  28. #define N  1000005
  29. ll cnt;
  30. pii trie[N][2];
  31. void reset()
  32. {
  33.     cnt=1;
  34.     rep(i,0,N)
  35.     {
  36.         trie[i][0].F=-1;
  37.         trie[i][0].S=0;
  38.         trie[i][1].S=0;
  39.         trie[i][1].F=-1;
  40.     }
  41.     return;
  42. }
  43. void insert(ll n)
  44. {
  45.     ll p=0;
  46.     while(n!=0)
  47.     {
  48.         if(trie[p][n&1].F!=-1)
  49.         {
  50.             trie[p][n&1].S++;
  51.             p=trie[p][n&1].F;
  52.         }
  53.         else
  54.         {
  55.             trie[p][n&1].S=1;
  56.             trie[p][n&1].F=cnt;
  57.             p=cnt;
  58.             cnt++;
  59.         }
  60.         n/=2;
  61.     }
  62.     return;
  63. }
  64. ll query(ll n)
  65. {
  66.     ll p=0,ans=0;
  67.     while(n!=0)
  68.     {
  69.         ans=ans<<1;
  70.         if(trie[p][!(n&1)].F!=-1)
  71.         {
  72.             ans++;
  73.             p=trie[p][!(n&1)].F;
  74.         }
  75.         else
  76.         {
  77.             p=trie[p][(n&1)].F;
  78.         }
  79.         n/=2;
  80.     }
  81.     return ans;
  82. }
  83. int main()
  84. {
  85.     ios_base::sync_with_stdio(false);
  86.     cin.tie(0);
  87.     cout.tie(0);
  88.     int TESTS=1;
  89.     cin>>TESTS;
  90.     while(TESTS--)
  91.     {
  92.         reset();
  93.         ll n;
  94.         cin>>n;
  95.         vi v(n);
  96.         ll mx=0;
  97.         rep(i,0,n)
  98.         {
  99.             cin>>v[i];
  100.         }
  101.         rep(i,1,n)
  102.         {
  103.             v[i]^=v[i-1];
  104.             mx=max(v[i],mx);
  105.         }
  106.         rep(i,0,n)
  107.         {
  108.             insert(v[i]);
  109.             mx=max(query(v[i]),mx);
  110.         }
  111.         cout<<mx<<endl;
  112.     }
  113.     return 0;
  114. }
Add Comment
Please, Sign In to add comment