Cod sursa(job #20035)

Utilizator szakiold name szaki Data 20 februarie 2007 16:56:39
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 kb
#include <stdio.h>
#include <stdlib.h>
//#include <mem.h>

#define BufSize 100001
//#define BufSize 10000
#define DMax 22 // Depth

long x[BufSize], n;
long xormax=-1, imax, jmax;
int maxlen;

typedef struct bsuf_tree {
	struct bsuf_tree *next[2];// 0/1
	int poz;
} ELEM;
ELEM *root, *branch;
int ibranch=-1;

inline ELEM* insert(long d);
void megold(long i);

void beolvas()
{
	ELEM *p;
	long i, c;
	freopen("xormax.in","r",stdin);
	freopen("xormax.out","w",stdout);

	scanf("%ld", &n);
	for (i=1; i<=n; i++)
	{
		scanf("%ld", &c);
		x[i]=c^x[i-1];
		p=insert(x[i]);
		if (p) p->poz=i;
		megold(i);
		if (x[i]>xormax) {xormax=x[i]; imax=i; jmax=0; }
	}
}

void init()
{
	root=new ELEM;
	root->next[0]=NULL;
	root->next[1]=NULL;
	branch=root;
}

inline ELEM* insert(long d)
{
	int i,l;
	int a[DMax];
	ELEM *p=root, *q;

	for (i=0; d > 0; i++)
	{
		a[i]=d&1;
		d>>=1;
	}
	l=i;
	for (; i<DMax; i++)
		a[i]=0;
	for (i=DMax-1; i>=0 && (p->next[a[i]])!=NULL; p=p->next[a[i--]])
			if (i > ibranch)
				if (p->next[1])
				{
					branch=p;
					ibranch=i;
				}
	//if (i<0) return NULL;
	for(; i>=0; i--)
	{
		q=(ELEM*)malloc(sizeof(ELEM));
		q->next[0]=NULL; q->next[1]=NULL; q->poz=-1;
		p->next[a[i]]=q;
		if (i > ibranch)
			if (p->next[1])
			{
				branch=p;
				ibranch=i;
			}
		p=q;
	}
	return p;
}

void list()
{
	ELEM *c[DMax+1];
	int k=0;
	char b[DMax+1];
	b[0]=0;
	c[0]=root;

	while (k>=0)
	{
		while (b[k]<=1)
		{
			if (c[k]->next[b[k]]!=NULL)
			{ c[k+1]=c[k]->next[b[k]]; b[k+1]=0; break; }
			b[k]++;
		}
		if (b[k]<=1) k++;
		else
		{
			if (c[k]->next[0]==NULL && c[k]->next[1]==NULL)
			{
				for (int i=0; i<k; i++)
					printf("%d", b[i]);
				printf("\n");
			}
			k--;
			b[k]++;
		}
	}
}

void shiftup()
{
	for(maxlen=DMax;root->next[1]==NULL && root->next[0]!=NULL; maxlen--,root=root->next[0]);
}

void megoldn2()
{
	for (int i=1; i<=n; i++)
		for (int j=i-1; j>=0; j--)
		{
			if ((x[i]^x[j])>xormax)
			{ xormax=x[i]^x[j]; imax=i; jmax=j; }
			if ((x[i]^x[j])==xormax && (imax-jmax)>i-j)
			{ xormax=x[i]^x[j]; imax=i; jmax=j;	}
		}
}

void megold(long i)
{
	long j, ti, tj;
	char c;
	//shiftup();
	ELEM *p;
//	for (i=1; i<=n; i++)
//	{
		p=branch;
		for (j=ibranch; j>=0; j--)
		{
			c=(x[i]>>j)&1;
			if (p->next[0] && p->next[1])
			{
				if (c==0) p=p->next[1];
				else p=p->next[0];
			}
			else
			{
				if (p->next[0]) p=p->next[0];
				else
				if (p->next[1]) p=p->next[1];
			}
		}

/*		if (i<p->poz) {ti=p->poz; tj=i;}
		else
		{ti=i; tj=p->poz;}*/
		ti=i; tj=p->poz;
		if (ti>tj)
		{
		if ((x[ti]^x[tj])>xormax)
		{ xormax=x[ti]^x[tj]; imax=ti; jmax=tj; }
		else
		if ((x[ti]^x[tj])==xormax)
			if ( ((imax-jmax)>ti-tj) || ( (imax-jmax)==ti-tj && ti < imax) )
			{ xormax=x[ti]^x[tj]; imax=ti; jmax=tj;	}
		}
//	}
}

void kiir()
{
	printf("%ld %ld %ld\n", xormax, jmax+1, imax);
}

int main()
{
	init();
	beolvas();
//	shiftup();
//	list();
//	megoldn2();
//	megold();
	kiir();
	return 0;
}