BoxerTC

Untitled

Jun 22nd, 2015
364
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 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 ) cerr <<  #x << "=" << x << endl;
  18. #define DEBUG2( x , y ) cerr << #x << "=" << x << " " << #y << "=" << y << endl;
  19.  
  20. #define N 18
  21. #define BITS 31
  22.  
  23. typedef long long ll;
  24. typedef pair< int , int > pii;
  25. typedef vector< int > vi;
  26. typedef vector< vi > vvi;
  27.  
  28. vvi dx = { {0 , 1} , {0 , -1} };
  29. vvi dy = { {1 , 0} , {-1 , 0} };
  30. int n;
  31. vi T[ 2 ][ N + 1 ][ N + 1 ];
  32. int A[N + 1][N + 1];
  33. bool valid( int x , int y ){
  34.     return x >= 0 && y >= 0 && x < n && y < n;
  35. }
  36. void back( int x , int y , int t , int cur ){
  37.     if( x + y == n - 1 ){
  38.         if( t ) cur ^= A[ x ][ y ];
  39.         T[ t ][ x ][ y ].pb( cur );
  40.         return;
  41.     }
  42.     REP( k , 2 ){
  43.         int nx = x + dx[ t ][ k ];
  44.         int ny = y + dy[ t ][ k ];
  45.         if( !valid( nx , ny ) ) continue;
  46.         int ncur = cur ^ A[ nx ][ ny ];
  47.         back( nx , ny , t , ncur );
  48.     }
  49. }
  50. int node;
  51. int NEXT[ BITS * (1<<18) + 5 ][ 2 ];
  52. void clear(){
  53.     node = 1;
  54.     clr( NEXT , 0 );
  55. }
  56. void add( int x ){
  57.     int p = 0;
  58.     for( int i = BITS - 1 ; i >= 0 ; --i ){
  59.         int cur = (x & (1 << i)) > 0;
  60.         if( !NEXT[ p ][ cur ] ) NEXT[ p ][ cur ] = node ++;
  61.         p = NEXT[ p ][ cur ];
  62.     }
  63. }
  64. int get( int x ){
  65.     int p = 0 , ans = 0;
  66.     for( int i = BITS - 1 ; i >= 0 ; --i ){
  67.         int cur = (x & (1 << i)) > 0;
  68.         if( NEXT[ p ][ cur ^ 1 ] ){
  69.             ans |= (1 << i);
  70.             p = NEXT[ p ][ cur ^ 1 ];
  71.             continue;
  72.         }
  73.         if( NEXT[ p ][ cur ] ){
  74.             p = NEXT[ p ][ cur ];
  75.             continue;
  76.         }
  77.         assert( 0 );
  78.     }
  79.     return ans;
  80. }
  81. void impr( vi &v ){
  82.     for( auto x : v ) cout << x << " "; cout << endl;
  83. }
  84. int main(){
  85.     while( sc( n ) == 1 ){
  86.         REP( i , n ) REP( j , n ) sc( A[ i ][ j ] );
  87.         back( 0 , 0 , 0 , A[ 0 ][ 0 ] );
  88.         back( n - 1 , n - 1 , 1 , A[ n - 1 ][ n - 1 ] );
  89.         int ans = -1;
  90.         REP( x , n ){
  91.             int y = n - 1 - x;
  92.             clear();
  93.             //REP( t , 2 ) assert( SZ(T[ t ][ x ][ y ]) < BITS * (1<<18) + 5 );
  94.             for( auto z : T[ 0 ][ x ][ y ] ) add( z );
  95.             for( auto z : T[ 1 ][ x ][ y ] ) ans = max( ans , get( z ) );
  96.         }      
  97.         printf( "%d\n" , ans );
  98.     }
  99. }
Advertisement
Add Comment
Please, Sign In to add comment