Cod sursa(job #81616)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 3 septembrie 2007 14:52:29
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <cstdio>

#define FIN "xormax.in"
#define FOUT "xormax.out"
#define MAX 100001
#define bit(x,i) ((x>>i)&1)
#define __debug__ 0

long A[MAX], P[MAX];
long i,n;
long max;
long st, fi;

class trie {
public: 
	struct nod {
		long *fin;
		nod *f[2];
	};
private: 
	nod* root; 
	long H;
	nod* creeaza() {
		nod* p = new nod;
		p -> f[0] = p->f[1] = 0;
		p->fin = 0;
		return p;
	}
public:
	trie(long height) {
		H = height;
		root = creeaza();
	}
	void add(long x, long pos) {
		long i;
		if ( __debug__ )
			printf(" Adding... ");
		nod *p = root;
		for (i=H-1; i>=0; --i) {
			if ( p->f[ bit(x,i) ] ) {
				if ( __debug__ ) 
					printf("%ld", bit(x,i));
				p = p->f[ bit(x,i) ];
			}
			else {
				p->f[ bit(x,i) ] = creeaza();
				p = p->f[ bit(x,i) ];
				if ( __debug__ ) 
					printf("(%ld)", bit(x,i));
			}
		}
		if ( __debug__ ) 
			printf(" --> %ld\n", x);
		p -> fin = new long;
		*(p->fin) = pos;
	};
	bool search(long x) {
		long i;
		nod *p = root;
		for (i=H-1; i>=0; --i) {
			if ( p->f[ bit(x,i) ] )
				p = p->f[ bit(x,i) ];
			else 
				return false;
		}
		return (p -> fin)!=0;
	};
	long search_l(long x) {
		long i;
		nod *p = root;
		if ( __debug__ )
			printf(" Searching(%ld)... ",x);
		for (i=H-1; i>=0; --i) {
			if ( p->f[ !bit(x,i) ] ) {
				p = p->f[ !bit(x,i) ];
				if ( __debug__ )
					printf("%ld",!bit(x,i));
			}
			else  {
				p = p->f[ bit(x,i) ];
				if ( __debug__ )
					printf("(%ld)",bit(x,i));
			}
		}
		if ( __debug__ )
			printf(" == %ld\n", *(p->fin));
		return *(p->fin);
	}
} T(22);

int main() {
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);
	
	scanf("%ld", &n);
	for (i=0; i<n; ++i) {
		scanf("%ld", A+i);
		if ( !i ) 
			P[i] = A[i];
		else
			P[i] = P[i-1] ^ A[i];
		T.add(P[i],i);
		long tmp = T.search_l(P[i]);
		if ( __debug__ )
			printf("Max: %5ld Act:%5ld\n", max, P[i]^P[tmp]);
		if ( max<P[i]^P[tmp] ) {
			max = P[i]^P[tmp];
			st = tmp+1;
			fi = i;
		}
	}
	
	printf("%ld %ld %ld\n", max, st+1, fi+1);
	
	fclose(stdout);fclose(stdin);
	return 0;
}