Pagini recente » Cod sursa (job #1061661) | Cod sursa (job #2122428) | Cod sursa (job #1449858) | Monitorul de evaluare | Cod sursa (job #948351)
Cod sursa(job #948351)
#include<fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int i,n,x,sol,pi,pf,a[100100];;
struct trie{
int poz;
trie *zero,*unu;
trie()
{
zero=unu=NULL;
poz=0;
}
};
trie *t=new trie;
void insereaza(trie *t,int p,int x)
{
if(p<0)
{
t->poz=i;
return ;
}
if(x&(1<<p))
{
if(!(t->unu))
{
t->unu=new trie;
insereaza(t->unu,p-1,x);
}
else
{
insereaza(t->unu,p-1,x);
}
}
else
{
if(!(t->zero))
{
t->zero=new trie;
insereaza(t->zero,p-1,x);
}
else
{
insereaza(t->zero,p-1,x);
}
}
}
void actualizeaza_solutia(trie *t,int p,int x)
{
if(p<0)
{
if(sol<(a[t->poz]^a[i]))
{
sol=a[t->poz]^a[i];
pi=t->poz+1;
pf=i;
}
return ;
}
if(x&(1<<p))
{
if(!(t->zero))
actualizeaza_solutia(t->unu,p-1,x);
else
actualizeaza_solutia(t->zero,p-1,x);
}
else
{
if(!t->unu)
actualizeaza_solutia(t->zero,p-1,x);
else
actualizeaza_solutia(t->unu,p-1,x);
}
}
int main()
{
f>>n;
sol=-1;
insereaza(t,21,0);
for(i=1;i<=n;++i)
{
f>>x;
a[i]=a[i-1]^x;
actualizeaza_solutia(t,21,a[i]);
insereaza(t,21,a[i]);
}
g<<sol<<' '<<pi<<' '<<pf<<'\n';
return 0;
}