Pagini recente » Cod sursa (job #2682984) | Cod sursa (job #384726) | Cod sursa (job #2694510) | Cod sursa (job #2682979) | Cod sursa (job #3356561)
#include <fstream>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
const int BitiMax=20;
const int NoduriMax=2100000;
class Trie {
public:
int copii[NoduriMax][2];
int nrr[NoduriMax];
int cnt;
Trie() {
cnt=1;
copii[1][0]=copii[1][1]=0;
nrr[1]=0;
}
} t;
void insert(int val, int index)
{
int nod=1;
t.nrr[nod]=index;
for (int bit=BitiMax;bit>=0;bit--)
{
int b=(val>>bit)&1;
if (t.copii[nod][b]==0)
{
t.copii[nod][b]=++t.cnt;
t.copii[t.cnt][0]=t.copii[t.cnt][1]=0;
}
nod=t.copii[nod][b];
t.nrr[nod]=index;
}
}
pair<int, int> gasestemax(int val)
{
int nod=1;
int ls=0;
for (int bit=BitiMax;bit>=0;bit--)
{
int b=(val>>bit)&1;
if (t.copii[nod][1-b])
{
ls+=(1<<bit);
nod=t.copii[nod][1-b];
}
else
nod=t.copii[nod][b];
}
return {ls,t.nrr[nod]};
}
int main()
{
int n,sumcur=0,max=-1,ls=1,ld=1;
fin>>n;
insert(0,0);
for (int j=1;j<=n;j++)
{
int x;
fin>>x;
sumcur^=x;
pair<int, int> rez=gasestemax(sumcur);
int maxcur=rez.first;
int lsmax=rez.second;
if (maxcur>max)
{
max=maxcur;
ls=lsmax+1;
ld=j;
}
insert(sumcur, j);
}
fout<<max<<" "<<ls<<" "<<ld;
return 0;
}