Cod sursa(job #159245)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 00:12:50
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 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;
}