Pagini recente » Cod sursa (job #1126541) | Cod sursa (job #2214233) | Cod sursa (job #485550) | Cod sursa (job #1136494) | Cod sursa (job #2026354)
#include<fstream>
using namespace std;
int v[100007] , sp[100007];
struct trie
{
trie *z,*u;
int urb;
trie()
{
z=NULL;
u=NULL;
urb=0;
}
}*rad;
trie *adaos(int X, int bit, trie *nod)
{
if(nod == NULL)
{
nod = new trie;
}
if(bit == -1)
{
nod -> urb = X;
return nod;
}
int fiu = sp[X] & (1<<bit);
if(fiu == 0)
{
nod -> z = adaos(X,bit-1,nod -> z);
}
else
{
nod -> u = adaos(X,bit-1,nod -> u);
}
return nod;
}
int cauta(int val, int bit, trie *nod)
{
if(bit==-1)
{
return nod -> urb;
}
int fiu = val & (1<<bit);
if(fiu==0)
{
if(nod -> u != NULL)
{
return cauta(val, bit-1, nod->u);
}
else
{
return cauta(val, bit-1, nod->z);
}
}
else
{
if(nod -> z != NULL)
{
return cauta(val, bit-1, nod->z);
}
else
{
return cauta(val, bit-1, nod->u);
}
}
}
int main()
{
ifstream read("xormax.in");
ofstream write("xormax.out");
int n,cpdr(0),cpst(0);
unsigned long long int maxxor=0;
read>>n;
for(int i=1;i<=n;++i)
{
read>>v[i];
sp[i] = sp[i-1] ^ v[i];
}
rad=adaos(0, 21, rad);
for(int i=1;i<=n;++i)
{
int gasit=cauta(sp[i], 21, rad);
if( (sp[gasit] ^ sp[i]) > maxxor)
{
maxxor = sp[gasit] ^ sp[i];
cpdr = i;
cpst = gasit + 1;
}
rad = adaos(i, 21, rad);
}
write << maxxor << " " << cpst << " " << cpdr ;
return 0;
}