Advertisement
Guest User

Untitled

a guest
Jul 17th, 2017
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3.  
  4. typedef long long llint;
  5. int N; llint a[ 100005 ];
  6.  
  7. struct node { node *c[ 2 ]; };
  8. node *root;
  9.  
  10. void update( node *n, int p, llint x ) {
  11.    if( p < 0 ) return;
  12.    if( !n->c[(x>>p)&1] ) n->c[(x>>p)&1] = new node();
  13.    update( n->c[(x>>p)&1], p-1, x );
  14. }
  15. llint query( node *n, int p, llint x ) {
  16.    if( p < 0 ) return 0;
  17.    if( n->c[!((x>>p)&1)] ) return query( n->c[!((x>>p)&1)], p-1, x )^(1LL<<p);
  18.    return query( n->c[(x>>p)&1], p-1, x );
  19. }
  20.  
  21. int main( void )
  22. {
  23.    root = new node();
  24.    scanf( "%d", &N );
  25.  
  26.    for( int i = 0; i < N; ++i ) {
  27.       scanf( "%lld", a+i );
  28.       update( root, 60, a[i] );
  29.    }
  30.  
  31.    for( int i = 0; i < N; ++i )
  32.       printf( "%lld\n", query( root, 60, a[i] ) );
  33.  
  34.    return 0;
  35. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement