Cod sursa(job #590934)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 21 mai 2011 14:04:41
Problema Xor Max Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include<stdio.h>

#define maxN 100005
#define bytmax 5

FILE*f=fopen("xormax.in","r");
FILE*g=fopen("xormax.out","w");

int n,i,A[maxN],b,x,y,q,poz,xormax = -1,pozmax1,pozmax2;

struct Trie{
	int poz;
	Trie *Byt[2];
	Trie () {
		poz = 0;
		Byt[0] = Byt[1] = NULL;
	}
};

Trie *r = new Trie;

void insert ( Trie *nod , int nb ){
	if ( !(nb + 1) ){
		nod->poz = i;
		return ;
	}
	
	b = (x & ( 1 << nb )) != 0;
	if ( nod->Byt[b] == NULL ){
		nod->Byt[b] = new Trie;
	}
	
	insert( nod->Byt[b] , nb - 1 );
}

int query ( Trie *nod , int nb ){
	if ( !(nb + 1) ){
		poz = nod -> poz;
		return 0;
	}
	
	b = (x & ( 1 << nb )) != 0;
	if ( nod->Byt[!b] )
		return ( (1 << nb) + query( nod->Byt[!b] , nb - 1 ) );
	else
		if ( nod->Byt[b] )
			return ( query( nod->Byt[b] , nb - 1 ) );
	
	poz = nod -> poz;
	
	return 0;
}


int main () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d",&A[i]);
	}
	
	i = 0; insert(r,bytmax-2);
	
	for ( i = 1 ; i <= n ; ++i ){
		x = A[i] ^ y;
		
		q = query(r,bytmax-2);
		if ( q > xormax || ( q == xormax && (poz + 1 < pozmax1) ) ){
			xormax = q;
			pozmax1 = poz + 1;
			pozmax2 = i;
		}
		
		insert(r,bytmax-2);
		y = x;
	}
	
	fprintf(g,"%d %d %d\n",xormax,pozmax1,pozmax2);
	
	fclose(f);
	fclose(g);
	
	return 0;
}