Cod sursa(job #45697)

Utilizator arenakadaffKadaff arenakadaff Data 1 aprilie 2007 20:15:34
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>


long int *v , *poz ;


int main()
{
	long int n , i , j , k , max , x , y , nr , sem ;
	FILE *in , *out ;
	in = fopen("xormax.in" , "rt") ;
	out = fopen("xormax.out" , "wt") ;
	v =(long int *) malloc(100010 * sizeof(long int)) ;
	poz = (long int *) malloc(8400000 * sizeof(long int)) ;
	fscanf(in , "%ld" , &n) ;
	fscanf(in , "%ld" , (v + 1)) ;
	j = 1 ;
	for(i = 0 , j = j << 21 ; i <= j ; i++) poz[i] = 0 ;
	k = 1 ;
	for(k = k << 20 , j = 1 ; k > 0 ; k = k >> 1)
	{
		if(v[1] & k)
		{
			j = j * 2 + 1 ;
			poz[j] = 1 ;
		}
		else
		{
			j = j * 2 ;
			poz[j] = 1 ;
		}
	}
	for(i = 2 , max = v[1] , x = 1 , y = 1 , sem = 0 ; i <= n ; i++ , sem = 0)
	{
		fscanf(in , "%ld" , &nr) ;
		v[i] = v[i-1] ^ nr ;
		k = 1 ;
		for(k = k << 20 , j = 1 ; k > 0 ; k = k >> 1)
		{
			if(!(v[i] & k))
			{
				if(poz[j * 2 + 1]) j = j * 2 + 1 ;
				else j *= 2 ;
			}
			else
			{
				if(poz[j * 2]) j *= 2 ;
				else j = j * 2 + 1 ;
			}
		}
		if(nr > max)
		{
			max = nr ;
			x = i ;
			j = i ;
		}
		if(v[i] > max)
		{
			max = v[i] ;
			x = 1 ;
			y = i ;
			sem = 1 ;
		}
		if((v[poz[j]] ^ v[i]) > max)
		{
			max = v[i] ^ v[poz[j]] ;
			x = poz[j] + 1 ;
			y = i ;
		}
		k = 1 ;
		for(k = k << 20 , j = 1 ; k > 0 ; k = k >> 1)
		{
			if(v[i] & k)
			{
				j = j * 2 + 1 ;
				poz[j] = i ;
			}
			else
			{
				j = j * 2 ;
				poz[j] = i ;
			}
		}
	}
	free(v) ;
	free(poz) ;
	fprintf(out , "%ld %ld %ld" , max , x , y) ;
	fclose(out) ;
	fclose(in) ;
	return 0 ;
}