Cod sursa(job #1481453)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 4 septembrie 2015 15:44:58
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.62 kb
#include<iostream>
#include<fstream>
#include<string.h>
#include<stdlib.h>
using namespace std;

#define NMAX 100001
#define LMAX 21

struct trie {
	trie *st,*dr;
	trie () {
		st=NULL;
		dr=NULL;
	}
};

char sir[LMAX+1];
int v[NMAX],x[NMAX];

inline int BIT(int x, int nr)
{
	return (x & (1<<nr)) != 0;
}

trie* aloca()
{
	trie *p;
	p=(trie*)malloc(sizeof(trie));
	p->st=NULL;
	p->dr=NULL;
	return p;
}

void adauga(trie *p, char *s)
{
	if(*s=='\0') {
		return ;
	}
	if(*s=='0') {
		if(p->st==NULL)
			p->st=aloca();
		adauga(p->st,s+1);
	}
	else if(*s=='1') {
		if(p->dr==NULL)
			p->dr=aloca();
		adauga(p->dr,s+1);
	}
}

int maxim(trie *p, char *s, int bit)
{
	if(*s=='\0')
		return 0;
	if(*s=='0') {
		if(p->dr!=NULL)
			return (1<<bit)+maxim(p->dr,s+1,bit-1);
		return maxim(p->st,s+1,bit-1);
	}
	else {
		if(p->st!=NULL)
			return (1<<bit)+maxim(p->st,s+1,bit-1);
		return maxim(p->dr,s+1,bit-1);
	}
}

int main ()
{
	int n,i,sol,j,val,stop;
	trie *p;
	ifstream f("xormax.in");
	ofstream g("xormax.out");
	f>>n;
	for(i=1;i<=n;i++)
		f>>v[i];
	f.close();
	for(i=1;i<=n;i++)
		x[i]=x[i-1]^v[i];
	sol=-(1<<30);
	memset(sir,0,sizeof(sir));
	p=aloca();
	for(i=0;i<=LMAX-1;i++)
		sir[i]='0';
	adauga(p,sir);
	for(i=1;i<=n;i++) {
		memset(sir,0,sizeof(sir));
		for(j=0;j<=LMAX-1;j++)
			if(BIT(x[i],j))
				sir[LMAX-1-j]='1';
			else sir[LMAX-1-j]='0';
		val=maxim(p,sir,LMAX-1);
		if(val>sol) {
			sol=val;
			stop=i;
		}
		adauga(p,sir);
	}
	for(i=stop;i>=1;i--)
		if((x[i]^x[stop])==sol) 
			break;
	g<<sol<<" "<<i+1<<" "<<stop;
	g.close();
	return 0;
}