Cod sursa(job #45449)

Utilizator arenakadaffKadaff arenakadaff Data 1 aprilie 2007 15:24:55
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <stdio.h>
#include <stdlib.h>


long int *v , *poz ;


int main()
{
	long int n , i , j , k , max , x , y , nr ;
	FILE *in , *out ;
	in = fopen("xormax.in" , "rt") ;
	out = fopen("xormax.out" , "wt") ;
	v =(long int *) malloc(200010 * sizeof(long int)) ;
	poz = (long int *) malloc(4200000 * sizeof(long int)) ;
	fscanf(in , "%ld" , &n) ;
	fscanf(in , "%ld" , (v + 1)) ;
	j = 1 ;
	for(i = 1 , 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 ; i <= n ; i++)
	{
		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(v[i] > max)
		{
			max = v[i] ;
			x = 1 ;
			y = i ;
		}
		if(v[j] ^ v[i] > max)
		{
			max = v[i] ^ v[j] ;
			x = 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 ;
			}
		}
	}
	fprintf(out , "%ld %ld %ld" , max , x , y) ;
	fclose(out) ;
	fclose(in) ;
	return 0 ;
}