Pagini recente » Cod sursa (job #2804746) | Cod sursa (job #1725894) | Cod sursa (job #2600575) | Cod sursa (job #1528716) | Cod sursa (job #2026371)
#include <fstream>
using namespace std;
int n,st,dr,rasp,sp[100011];
struct trie
{
trie *z,*u;
int who;
trie ()
{
z=NULL;
u=NULL;
}
}*nod;
trie*insert (int i, int bit ,trie*nod)
{
if (nod==NULL)
{
nod = new trie;
}
if (bit==-1)// am terminat toti biti
{
nod->who=i;
return nod;
}
int fin=sp[i]&(1<<bit);
if (fin==0)
{
nod->z=insert(i,bit-1,nod->z);
}
else
{
nod->u=insert(i,bit-1,nod->u);
}
}
int find (int val , int bit , trie *nod)
{
if (bit==-1)
{
return nod->who;
}
int fin=val&(1<<bit);//fin==0 sau 2
if (fin==0)
{
if (nod->u!=NULL)
{
return find(val,bit-1,nod->u);
}
else
{
return find(val,bit-1,nod->z);
}
}
else
{
if (nod->z!=NULL)
{
return find (val,bit-1,nod->z);
}
else
{
return find (val,bit-1,nod->u);
}
}
}
int main()
{
ifstream fin ("xormax.in");
ofstream fout ("xormax.out");
fin>>n;
for(int i = 1; i <= n; ++ i)
{
int x;
fin>>x;
sp[i]=sp[i-1]^x;
}
nod=insert(0,21,nod);
for (int i=1;i<=n;++i)
{
int gasit=find(sp[i],21,nod);
if ((gasit^sp[i])>rasp)
{
rasp=gasit^sp[i];
dr=i;
st=gasit+1;
}
nod=insert(i,21,nod);
}
fout<<rasp<<" "<<st<<" "<<dr;
}