Cod sursa(job #397975)

Utilizator g3ppyStoian Vlad g3ppy Data 17 februarie 2010 19:43:27
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <stdio.h>
#include <stdlib.h>
#define NMAX 100005
#define llong int
FILE *fin,*fout;

struct trie{
	llong ind;
	trie *z,*u;
};

trie * t;

llong a[NMAX], sum[NMAX];
llong start[NMAX],end[NMAX],max;
llong n;


void addTrie (trie * t, llong indice, llong n, llong biti)
{trie *p, *q;
llong i, l = 0;;

	p = t;
	for (i = 1; i <= biti; i++)
	{
		l = l << 1;
		l = l ^ ( n & 1 );
		n = n >> 1;
	}
	n = l;
	for (i = 1; i <= biti; i++)
	{
		l = n & 1;
		
		
		if ( l == 1 )
		{
			if ( i == biti && p -> u == NULL)
			{
				q = (trie *) malloc(sizeof(trie));
				q -> z = q -> u = NULL;
				q -> ind = indice;
				p -> u = q;
			}
			else if (p -> u == NULL)
			{
				q = (trie *) malloc(sizeof(trie));
				q -> z = q -> u = NULL;
				q -> ind = 0;
				p -> u = q;
			}
			p = p -> u;
		}
		else{
			if ( i == biti && p -> z == NULL)
			{
				q = (trie *) malloc(sizeof(trie));
				q -> z = q -> u = NULL;
				q -> ind = indice;
				p -> z = q;
			}
			else if (p -> z == NULL)
			{
				q = (trie *) malloc(sizeof(trie));
				q -> z = q -> u = NULL;
				q -> ind = 0;
				p -> z = q;
			}
			p = p -> z;
			
		}
		
		n = n >> 1;
	}
	
}


llong findTrie (trie * t, llong n, llong biti)
{trie *p;
llong i, l = 0;

	p = t;
	
	for (i = 1; i <= biti; i++)
	{
		l = l << 1;
		l = l ^ ( n & 1 );
		n = n >> 1;
	}
	n = l;
	
	for (i = 1; i <= biti; i++)
	{
		l = n & 1;
		
		if ( l == 0 )
		{
			if ( p -> u != NULL)
			{
				p = p -> u;
			}
			else p = p -> z;
		}
		else{
			if ( p -> z != NULL)
			{
				p = p -> z;
			}
			else p = p -> u;
		}
		
		n = n >> 1;
	}
return p -> ind;
}


int  main()
{llong i, biti, indMax, j;
	fin = fopen ("xormax.in","rt");
	fout = fopen ("xormax.out","wt");
	
	fscanf(fin,"%d",&n);
	max = 1;
	for (i = 1; i <= n; i++)
	{
		fscanf(fin,"%d",&a[i]);
		sum[i] = sum[i-1] ^ a[i];
		if (max < sum[i]) max = sum[i];
	}
	
	if ( n == 1)
	{
		fprintf(fout,"1 1 %d\n",sum[1]);
		return 0;
	}
	
	i = 0;
	while (max)
	{
		max = max >> 1;
		i++;
	}
	biti = i;
	
	max = -1;
	
	t = (trie *) malloc(sizeof(trie));
	
	t -> ind = 0;
	t -> z = t -> u = NULL;
	
	for (i = 1; i <= n; i++)
	{
		addTrie (t,i,sum[i],biti);
	}
	
	for (i = 1; i <= n; i++)
	{
		indMax = findTrie (t,sum[i],biti);
		
		//fprllongf(fout,"%d %d %d\n\n",i,indMax,sum[i] ^ sum[indMax]);
		
		if (indMax != i)
		{
			if ( (sum[i] ^ sum[indMax]) > max)
			{
				max = sum[i] ^ sum[indMax];
				j = 0;
				if ( i > indMax)
				{
					
					start[j] = indMax;
					end[j] = i;
				}
				else{
					start[j] = i;
					end[j] = indMax;
				}
				j = 1;
				
			}	
			else if ( (sum[i] ^ sum[indMax]) == max )
			{
				if ( i > indMax)
				{
					start[j] = indMax;
					end[j] = i;
				}
				else
				{
					start[j] = i;
					end[j] = indMax;
				}
				j++;
			}
		}
	}
	
	indMax = 0;
	for (i = 0 ; i < j; i++)
	{
		if ( end[i] < end[indMax] ) indMax = i;
	}
	
	for (i = 0; i < j; i++)
	{
		if ( i != indMax && end[i] == end[indMax] && start[i] > start[indMax] ) indMax = i;
	}
	
	
	fprintf(fout,"%d %d %d\n",max,start[indMax]+1,end[indMax]);
	fclose(fin);
	fclose(fout);	
return 0;	
}