Advertisement
Guest User

XOR SUM

a guest
Jan 17th, 2015
299
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.30 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <climits>
  5. #include <cstring>
  6.  
  7. #include <queue>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11.  
  12. #include <iostream>
  13. #include <iterator>
  14. #include <string>
  15. #include <algorithm>
  16. #include <functional>
  17. #include <utility>
  18.  
  19.  
  20. #define MOD 1000000007
  21. #define PI 3.1415926535897932384626433832795
  22. #define INF LONG_MAX
  23. #define X first
  24. #define Y second
  25. #define pb push_back
  26. #define gc() getchar()
  27.  
  28. using namespace std;
  29.  
  30. inline void fastRead_int(int &x) {
  31.     register int c = gc();
  32.     x = 0;
  33.     int neg = 0;
  34.     for(; ((c<48 || c>57) && c != '-'); c = gc());
  35.     if(c=='-') {
  36.         neg = 1;
  37.         c = gc();
  38.     }
  39.     for(; c>47 && c<58 ; c = gc()) {
  40.         x = (x<<1) + (x<<3) + c - 48;
  41.     }
  42.     if(neg)
  43.         x = -x;
  44. }
  45. struct node
  46. {
  47.     int value = -1;
  48.     struct node *child[2] = {NULL};
  49. };
  50.  
  51. node *head = NULL;
  52.  
  53. void insert_trie(int x)
  54. {
  55.     int base = 0x00200000;
  56.     node *current = head;
  57.     while(base)
  58.     {
  59.         int digit = base&x;
  60.         digit = (digit == 0)?0:1;
  61.         if(current->child[digit] == NULL)
  62.             current->child[digit] = new node();
  63.         current = current->child[digit];
  64.         base>>=1;
  65.     }
  66.     current->value = x;
  67. }
  68.  
  69. int query_trie(int x)
  70. {
  71.     node *current = head;
  72.     int base = 0x00200000;
  73.     while(base)
  74.     {
  75.         int digit = base&x;
  76.         digit = (digit == 0)?0:1;
  77.         if(current->child[abs(1-digit)] == NULL)
  78.             current = current->child[digit];
  79.         else
  80.             current = current->child[abs(1-digit)];
  81.  
  82.         base>>=1;
  83.     }
  84.     return current->value;
  85. }
  86.  
  87. int main(void)
  88. {  
  89.     #ifndef ONLINE_JUDGE
  90.         freopen("in.txt", "r", stdin);
  91.     #endif
  92.    
  93.  
  94.     int t,n,tmp;
  95.     fastRead_int(t);
  96.     while(t--)
  97.     {
  98.         fastRead_int(n);
  99.         vector<int> arr(n);
  100.         int maxx = 0;
  101.         int maxIndx;
  102.         head = new node();
  103.  
  104.         for(int i=0;i<n;i++)
  105.             fastRead_int(arr[i]);
  106.  
  107.         tmp = 0;
  108.         for(int i=0;i<n;i++)
  109.         {
  110.             tmp = tmp^arr[i];
  111.             if(tmp >= maxx)
  112.             {
  113.                 maxx = tmp;
  114.                 maxIndx = i;
  115.             }
  116.         }
  117.  
  118.         int ans = 0,qr;
  119.         tmp = 0;
  120.         insert_trie(0);
  121.         for(int i=0;i<=maxIndx;i++)
  122.         {
  123.             tmp = tmp^arr[i];
  124.             insert_trie(tmp);
  125.             qr = query_trie(maxx);
  126.             ans = ((qr^maxx)>ans)?(qr^maxx):ans;
  127.  
  128.         }
  129.         printf("%d ", ans);
  130.         arr.clear();
  131.         head = NULL;
  132.     }
  133.     return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement