Cod sursa(job #936145)

Utilizator radu124Radu Stefan radu124 Data 5 aprilie 2013 17:45:37
Problema Xor Max Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

int32_t cnt[4194304];
/**
cnt[x] number of sequences of xorsum x
cnt[2097152+x/2] number of sequences of xorsum starting with first 20 bits of x
 */
int32_t v[100002];

int bases[21]=
	{0,         2097152,   3145728,   3670016,
	 3932160,   4063232,   4128768,   4161536,
	 4177920,   4186112,   4190208,   4192256,
	 4193280,   4193792,   4194048,   4194176,
	 4194240,   4194272,   4194288,   4194296,
	 4194300};

int n;

void addcnt(int x, int q)
{
	int base=0,i;
	for (i=0; i<21; i++)
	{
		cnt[base+x]+=q;
		x/=2;
		base+=1<<(21-i);
	}
}

int bestpos;
int best;
int crtbest;
int bestlast;

int findbest(x)
{
	int base=x^0x1fffff;
	int i;
	for (i=20; i>=0; i--)
	{
		int bbit=1<<i;
		int c0=cnt[bases[i]+(base>>i)];
		int c1=cnt[bases[i]+((base^bbit)>>i)];
		if (!c0)
		{
			base^=bbit;
		}
	}
	return x^base;
}

int main(int argc, char *argv[])
{
	int i,x;
	FILE *fin=fopen("xormax.in","r");
	fscanf(fin,"%d ",&n);
	for (i=0; i<n; i++) fscanf(fin,"%d ",&v[n-1-i]);
	memset(cnt,0,sizeof(cnt));
	fclose(fin);
	x=0;
	bestpos=0;
	best=0;
	for (i=0; i<n; i++)
	{
		x=x^v[i];
		addcnt(x,1);
	}
	x=0;
	for (i=0; i<n; i++)
	{
		crtbest=findbest(x);
		if (crtbest>=best)
		{
			best=crtbest;
			bestpos=i;
		}
		x=x^v[i];
		addcnt(x,-1);
	}
	bestlast=bestpos;
	x=0;
	crtbest=0;
	for (i=bestpos; i<n; i++)
	{
		x=x^v[i];
		if (x>crtbest)
		{
			crtbest=x;
			bestlast=i;
		}
	}
	FILE *fou=fopen("xormax.out","w");
	fprintf(fou,"%d %d %d",crtbest,n-bestlast,n-bestpos);
	fclose(fou);
}