Cod sursa(job #20637)

Utilizator victor_u_roVictor Ungureanu victor_u_ro Data 21 februarie 2007 20:52:04
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMAX 100001
#define BMAX 32

long v[NMAX], n, max, imax, zmax;
struct nod {
	int end;
	nod *next[2];
} *r;

void cit()
{
	freopen("xormax.in", "rt", stdin);
	long i, x;

	scanf("%ld", &n);
	v[0] = 0;
	for (i = 1; i <= n; i++)
	{
		scanf("%ld", &x);
		v[i] = v[i - 1] ^ x;
	}

	fclose(stdin);
}

void init(nod *&p)
{
	p = NULL;
	p = (nod *) malloc(sizeof(nod));
	p->end = 0;
	p->next[0] = p->next[1] = NULL;
}

void bit(int x, int (&y)[BMAX])
{
	int i = 0;

	memset(y, 0, BMAX * sizeof(int));
	while (x > 0)
	{
		y[ ++i ] = x % 2;
		x /= 2;
	}
}

void add(long x)
{
	int y[BMAX], i;
	nod *p, *q;

	bit(x, y);
	for (p = r, i = BMAX - 1; i >= 1; i--)
	{
		if (!p->next[ y[i] ])
		{
			init(q);
			p->next[ y[i] ] = q;
		}
		p = p->next[ y[i] ];
	}
}

void rez()
{
	long i;
	int y[BMAX], z[BMAX], j, yy, zz, p2;
	nod *p;

	init(r);
	for (i = 1; i <= n; i++)
		add(v[i]);
	for (i = 1; i <= n; i++)
	{
		bit(v[i], y);
		for (p = r, j = BMAX - 1; j >= 1; p = p->next[yy], j--)
		{
			yy = y[j] ^ 1;
			if (p->next[yy])
				z[j] = yy;
			else
				z[j] = yy = y[j];
		}
		for (zz = 0, p2 = 1, j = 1; j <= BMAX - 1; p2 *= 2, j++)
			zz += z[j] * p2;
		if (v[i] ^ zz > max)
		{
			max = v[i] ^ zz;
			imax = i;
			zmax = zz;
		}
	}
}

void afis()
{
	freopen("xormax.out", "wt", stdout);
	long i;

	printf("%ld ", max);
	for (i = imax; i >= 0 && zmax != v[i]; i--);
	printf("%ld %ld\n", i + 1, imax);
	fclose(stdout);
}

int main()
{
	cit();
	rez();
	afis();

	return 0;
}