BoxerTC

Untitled

Jun 21st, 2015
331
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define sc( x ) scanf( "%d" , &x )
  5. #define REP( i , n ) for( int i = 0 ; i < n ; i++ )
  6. #define clr( t , val ) memset( t , val , sizeof(t) )
  7.  
  8. #define all(v)  v.begin() , v.end()
  9. #define pb push_back
  10. #define SZ( v ) ((int)(v).size())
  11.  
  12. #define mp make_pair
  13. #define fi first
  14. #define se second
  15.  
  16. #define test puts("************test************");
  17. #define DEBUG( x ) cout <<  #x << "=" << x << endl;
  18. #define DEBUG2( x , y ) cout << #x << "=" << x << " " << #y << "=" << y << endl;
  19.  
  20. #define N 100000
  21. #define ALP 2
  22. #define LAST 31
  23.  
  24. typedef long long ll;
  25. typedef pair< int , int > pii;
  26. typedef vector< int > vi;
  27.  
  28. ll AC[ 34 * N + 5 ];
  29. int NEXT[ 34 * N + 5 ][ ALP ] , node;
  30.  
  31. void init(){
  32.     node = 1;
  33.     clr( NEXT , 0 );
  34. }
  35. void add( ll x ){
  36.     int p = 0;
  37.     for( int i = LAST ; i >= 0 ; --i ){
  38.         int cur = (x & (1LL << i)) > 0;
  39.         assert( cur <= 1 );
  40.         if( !NEXT[ p ][ cur ] ) NEXT[ p ][ cur ] = node++;
  41.         p = NEXT[ p ][ cur ];
  42.     }
  43. }
  44. ll get( ll x ){
  45.     int p = 0;
  46.     ll ans = 0;
  47.     for( int i = LAST ; i >= 0 ; --i ){
  48.         int cur = (x & (1LL << i)) > 0;
  49.         if( NEXT[ p ][ cur ^ 1 ] ){
  50.             ans |= (1LL << i);
  51.             p = NEXT[ p ][ cur ^ 1 ];
  52.             continue;
  53.         }
  54.         if( NEXT[ p ][ cur ] ){
  55.             p = NEXT[ p ][ cur ];
  56.             continue;
  57.         }
  58.         assert( 0 );
  59.         break;
  60.     }
  61.     return ans;
  62. }
  63. ////  1110011
  64. ////  00011
  65. int main(){
  66.     ios_base :: sync_with_stdio( 0 );
  67.     int cases;
  68.     cin >> cases ;
  69.     REP( tc , cases ){
  70.         init();
  71.         int n;
  72.         cin >> n;
  73.         ll maxi = 0;
  74.         add( 0LL );
  75.         REP( i , n ){
  76.             ll x;
  77.             cin >> x;
  78.             AC[ i + 1 ] = AC[ i ] ^ x;
  79.             ll y = get( AC[ i + 1 ] );
  80.             maxi = max( maxi , y );
  81.             add( AC[ i + 1 ] );
  82.         }
  83.         cout << maxi << '\n';
  84.     }
  85. }
Advertisement
Add Comment
Please, Sign In to add comment