Cod sursa(job #80049)

Utilizator cosminpdrfischer2004 cosminp Data 25 august 2007 17:48:39
Problema Xor Max Scor 70
Compilator c Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <stdio.h>
#include <stdlib.h> 
#include <string.h> 

#define MAXA 5000000
#define MAXN 100005

int A[MAXA], S[MAXN], B[25], nB = 21; 
int N; 

void binary(int n)
{
	int i = nB; 
	while (i >= 0)
		B[i--] = n%2, n /= 2; 
}


void add(int n, int ind)
{
	binary(n);
	int i, j = 0;

	for (i = 0; i < nB; i++)
		if (B[i] == 0)
			A[2*j+1] = 1, j = 2*j + 1;
		else 
			A[2*j+2] = 1, j = 2*j + 2; 
	A[j] = ind;
}	
	
int find(int n)
{
	int i, j = 0, v = 0; 
	
	binary(n);
	for (i = 0; i < nB; i++)
		if (B[i] == 0)
			if (A[2*j + 2] != -1) // pot sa merg dreapta
				v = 2*v + 1, j = 2*j + 2;
			else 
				v = 2*v, j = 2*j + 1; 
		else 
			if (A[2*j + 1] != -1) 
				v = 2*v, j = 2*j + 1; 
			else 
				v = 2*v + 1, j = 2*j + 2; 
	return A[j];
}
	
int main()
{
	int i, j, a, ip, iq, maxim; 
	
	memset(A, -1, sizeof(A)); 
	
	freopen("xormax.in", "rt", stdin);
	freopen("xormax.out", "wt", stdout); 
	
	scanf("%d", &N);
	
	S[0] = 0; 
	add(S[0], 0);
	maxim = -1;
	for (i = 1; i <= N; i++)
	{
		scanf("%d", &a);
		S[i] = S[i-1]^a;
		add(S[i], i);
		j = find(S[i]);
		if ((S[j]^S[i]) > maxim)
			maxim = (S[j]^S[i]), ip = j, iq = i;
	}
	fclose(stdin);
	
	printf("%d ", maxim);
	 
	printf("%d %d", ip+1, iq);
	fclose(stdout);	
	return 0;
}