Cod sursa(job #2240227)

Utilizator shantih1Alex S Hill shantih1 Data 12 septembrie 2018 19:36:44
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 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[25];

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)
{
	int l=19;
	for(int i=l;i>=0;i--)
	{
		if(x&(1<<i))	b[i]=1;
		else	b[i]=0;
	}
	bag(T, b+l);
	calc(T, b+l);
	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";
*/
	rez=0;
	for(i=1;i<=n;i++)
		for(int j=0;j<i;j++)
		{
			nr=v[i]^v[j];
			if(nr>rez)
			{
				rez=nr;
				a=j+1;	A=i;
			}
			if(nr==rez&&j+1>a&&i==A)	a=j+1;
		}
	fout<<rez<<"\n";
	fout<<a<<" "<<A<<"\n";
}