Cod sursa(job #2240164)

Utilizator shantih1Alex S Hill shantih1 Data 12 septembrie 2018 18:15:02
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");

int n,i,a,A,rez,c,xr,nr;
int v[100005];
bool b[22];

struct trie
{
	int id;
	trie *f[2];
	trie ()
	{
		id=0;
		f[0]=f[1]=0;
	}
};
trie *T = new trie;

void bag(trie *nd,bool *bl)
{
	if(bl==b)
	{	
		nd->id=i;
		return;
	}
	if(nd->f[*bl]==0)
		nd->f[*bl] = new trie;
	bag(nd->f[*bl], bl-1);
}

void calc(trie *nd,bool *bl)
{
	if(bl==b)
	{
		c=nd->id;
		return;
	}
	int y=(*bl==0)?1:0;
	if(nd->f[y]==0)	calc(nd->f[*bl], bl-1);
	else calc(nd->f[y], bl-1);
}

int gest(int x)
{
	for(int i=19;i>=0;i--)
	{
		if(x&(1<<i))	b[i]=1;
		else	b[i]=0;
	}
	bag(T, b+19);
	calc(T, b+19);
	int r=x^v[c];
	return r;
}

int main() {
	
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>v[i];
		if(v[i]>rez)
		{	rez=v[i];	a=A=i;	}
	}
	
	for(i=1;i<=n;i++)
	{
		v[i]^=v[i-1];
		nr=gest(v[i]);
		if(nr>rez)
		{
			rez=nr;
			a=c+1;	A=i;
		}
		if(v[i]>rez)
		{	rez=v[i];	a=1;	A=i;	}
	}
	fout<<rez<<"\n";
	fout<<a<<" "<<A<<"\n";
}