Cod sursa(job #474300)

Utilizator CS-meStanca Marian Ciprian CS-me Data 3 august 2010 12:46:07
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>

#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);
    freopen("xormax.out","w",stdout);
    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 ) {
            if ( m<(A[i]^A[p]) ) {
                st = p+1; dr = i; m = A[i]^A[p];
            }
        }
        trie_add(A[i], i);
    }
    printf("%ld %ld %ld\n", m, st,dr);
    return 0;
}