Cod sursa(job #142827)

Utilizator raula_sanChis Raoul raula_san Data 25 februarie 2008 12:56:55
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>

#define dim 100001
#define cnt 10

int N;
int M;
int Nst;
int Pos;

int Xmax;
int Imax;
int Jmax;
int Lmin;

int A[dim];
int T[dim*cnt];
int Trie[dim*cnt][2];

void ReadData();
void Build();
void BagaTrie(int, int);
void Solve();
void Write();

int Query(int v)
{
	int b, nb, ret, st;
	
	for(ret=st=0, nb=M-1; nb>=0; --nb)
	{
		b = (v >> nb) & 1;
		
		if(Trie[st][!b])
		{
			ret |= (1 << nb);
			st = Trie[st][!b];
		}
		else
			st = Trie[st][b];
	}
	Pos = st;
	
	return ret;
}

int main()
{
	ReadData();
	Build();
	Solve();
	Write();
	
	return 0;
}

void ReadData()
{
	freopen("xormax.in", "rt", stdin);
	
	int i, v, nb;
	for(scanf("%d", &N), i=1; i<=N; ++i)
	{
		scanf("%d", &v);
		A[i] = A[i-1] ^ v;
		
		nb = 0;
		while(v) ++ nb, v >>= 1;
		
		M = nb > M ? nb : M;
	}
	
	fclose(stdin);
}

void Build()
{
	int i;
	for(i=1; i<=N; ++i)
		BagaTrie(A[i], i);
		
	BagaTrie(0, 0);
}

void BagaTrie(int v, int pos)
{
	int st = 0, nb, b;
	
	for(nb=M-1; nb>=0; --nb)
	{
		b = (v >> nb) & 1;
		
		if(!Trie[st][b])
		{
			Trie[st][b] = ++ Nst;
			st = Nst;
		}
		else
			st = Trie[st][b];
	}
	
	if(!T[st]) T[st] = pos;
}

void Solve()
{
	int i, v;
	for(i=0; i<N; ++i)
	{
		v = Query(A[i]);

		if(T[Pos] <= i) continue;
		
		if(v > Xmax)
		{
			Xmax = v;
			Imax = i + 1;
			Jmax = T[Pos];
			Lmin = Jmax - i;
		}
		else if(v == Xmax && T[Pos] < Jmax)
		{
			Imax = i + 1;
			Jmax = T[Pos];
			Lmin = Jmax - i;
		}
		else if(v == Xmax && T[Pos] == Jmax && T[Pos] - i < Lmin)
		{
			Imax = i + 1;
			Lmin = T[Pos] - i;
		}
	}
}

void Write()
{
	freopen("xormax.out", "wt", stdout);
	
	printf("%d %d %d", Xmax, Imax, Jmax);
	
	int i, ok;
	
	if(Imax == Jmax)
		for(i=1, ok=0; i<=N; ++i)
			if(A[i] ^ A[i-1] == Xmax) ok = 1;
			
	if(!ok) for(;;);
	
	fclose(stdout);
}