Pagini recente » Cod sursa (job #2523621) | Cod sursa (job #2944522) | Cod sursa (job #1787177) | Cod sursa (job #1901601) | Cod sursa (job #1795481)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
struct Trie
{
int nr;
Trie *fiu[2];
Trie()
{
nr = -1;
fiu[1] = fiu[0] = 0;
}
};
Trie *t = new Trie;
const int Nmax = 100005;
int n, x[Nmax], xormax[Nmax], in, fi, s;
void Read()
{
f>>n;
for(int i = 1; i <= n; i++) f>>x[i];
}
void Print()
{
g<<s<<' '<<in<<' '<<fi<<'\n';
}
void Insert(Trie *nod, int val, int bit)
{
if(bit == -1)
{
nod -> nr = val;
return;
}
if(((1<<bit)&val) != 0)
{
if(nod->fiu[1] == 0)
nod ->fiu[1] = new Trie;
Insert(nod->fiu[1],val,bit-1);
}
else
{
if(nod->fiu[0] == 0)
nod ->fiu[0] = new Trie;
Insert(nod->fiu[0],val,bit-1);
}
}
int Query(Trie *nod, int val, int bit)
{
if(bit == -1)
return nod -> nr;
if(((1<<bit)&val) != 0)
{
if(nod->fiu[0] != 0)
return Query(nod->fiu[0],val,bit-1);
return Query(nod->fiu[1],val,bit-1);
}
else
{
if(nod->fiu[1] != 0)
return Query(nod->fiu[1],val,bit-1);
return Query(nod->fiu[0],val,bit-1);
}
}
int main()
{
int scur, Xor;
Read();
xormax[1] = x[1];
in = fi = 1;
scur = x[1];
Insert(t, scur, 21);
s = xormax[1];
for(int i = 2; i <= n; i++)
{
scur ^= x[i];
Xor = Query(t,scur,21);
xormax[i] = max(x[i], scur^Xor);
Insert(t,scur,21);
if(xormax[i] > s)
{
s = xormax[i];
fi = i;
}
}
Xor = x[fi];
in = fi;
for(int i = fi-1; i > 0 && Xor!=s; i--)
{
Xor ^= x[i];
in = i;
}
Print();
return 0;
}