Pagini recente » Cod sursa (job #1798568) | Cod sursa (job #2681053) | Cod sursa (job #281243) | Cod sursa (job #2158364) | Cod sursa (job #2049564)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
struct trie
{
trie *next[2];
int val;
}*d,*p;
int n,x[100005],val,in,Max=0,init,fi;
void mx(int val,int &sum,int &poz)
{
sum=0;
poz=0;
for(int i=21;i>=0;i--)
{
bool bit=(((1<<i)&val)!=0);
bool bit1=bit;
if(p->next[1-bit]!=0)
bit1=1-bit;
sum=sum*2+(bit^bit1);
poz=poz*2+bit1;
p=p->next[bit1];
}
}
void adauga(int val,int act)
{
for(int i=21;i>=0;i--)
{
bool bit=(((1<<i)&val)!=0);
if(p->next[bit]==0)
{
trie *s=new trie;
s->next[0]=0;
s->next[1]=0;
p->next[bit]=s;
p=s;
p->val=act+1;
}
else
{
p=p->next[bit];
p->val=act+1;
}
}
}
int main()
{
fin>>n;
d=new trie;
d->next[0]=0;
d->next[1]=0;
p=d;
for(int i=0;i<=21;i++)
{
trie *s=new trie;
s->next[0]=0;
s->next[1]=0;
p->next[0]=s;
p=s;
p->val=1;
}
int vi;
for(int i=1;i<=n;i++)
{
fin>>x[i];
p=d;
x[i]=x[i-1]^x[i];
mx(x[i],val,in);
if(Max<val)
{
Max=val;
vi=in;
fi=i;
}
p=d;
adauga(x[i],i);
}
for(int i=1;i<fi;i++)
if(vi==x[i]){
init=i+1;
}
fout<<Max<<" "<<init<<" "<<fi;
return 0;
}