Cod sursa(job #590879)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 20 mai 2011 21:04:26
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<stdio.h>

#define maxN 100005
#define bytmax 25

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) ){
		return ;
	}
	
	b = (x & ( 1 << nb )) != 0;
	if ( nod->Byt[b] == NULL ){
		nod->Byt[b] = new Trie;
		(nod->Byt[b])->poz = i;
	}
	
	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]);
	}
	
	x = A[1]; i = 1;
	insert(r,bytmax-2);
	y = x;
	
	for ( i = 2 ; i <= n ; ++i ){
		x = A[i] ^ y;
		
		q = query(r,bytmax-2);
		if ( q > xormax ){
			xormax = q;
			pozmax1 = poz + 1;
			pozmax2 = i;
		}
		if ( x > xormax ){
			xormax = x;
			pozmax1 = 1;
			pozmax2 = i;
		}
		
		insert(r,bytmax-2);
		y = x;
	}
	
	fprintf(g,"%d %d %d\n",xormax,pozmax1,pozmax2);
	
	fclose(f);
	fclose(g);
	
	return 0;
}