Cod sursa(job #164956)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 24 martie 2008 23:23:56
Problema Xor Max Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 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;
}