Cod sursa(job #160803)

Utilizator FlorinC1996Florin C FlorinC1996 Data 16 martie 2008 21:18:45
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.49 kb
 #include <cstdio>   
  
#define act ((x&i)?1:0)   
  
const long MAX = 100010;   
const long mx = 30;   
  
long m = -1, st,dr;   
long A[MAX];   
long n, i;   
  
struct trie {    
    long info;   
    trie *f[2];   
} *root = new trie;   
  
void trie_add(long x, long y) {   
    long i;   
    trie *r = root;   
  
    for (i=1<<mx; i; i>>=1) {   
        if ( !r->f[act] ) {   
            r->f[act] = new trie;   
            *(r->f[act]) = (trie){0,{0,0}};   
        }   
  
        r = r->f[act];   
    }   
    r->info = y;   
}   
  
int trie_search(long x) {    
    long i; trie *r = root;   
    for (i=1<<mx; i; i>>=1) {   
        if ( r->f[!act] ) {   
            r = r->f[!act];   
            continue ;   
        }   
        if ( r->f[act] ) {   
            r = r->f[act];   
            continue ;   
        }   
        return -1;   
    }   
    return r->info;   
}   
  
int main() {   
    freopen("xormax.in", "r", stdin);   
    scanf("%ld", &n);   
    trie_add(0,0);   
    for (i=1; i<=n; ++i) {    
        long x;    
        scanf("%ld", &x);   
        A[i] = A[i-1] ^ x;   
        long p = trie_search(A[i]);   
        if ( p!=-1 ) {              // found ok   
            if ( m<(A[i]^A[p]) ) {   
                st = p+1; dr = i; m = A[i]^A[p];   
            }   
        }   
        trie_add(A[i], i);   
    }   
  
    fprintf(fopen("xormax.out", "w"), "%ld %ld %ld\n", m, st,dr);   
    return 0;   
}