Pagini recente » Cod sursa (job #564164) | Cod sursa (job #2581583) | Cod sursa (job #1352335) | Cod sursa (job #1863429) | Cod sursa (job #3230796)
#include <bits/stdc++.h>
#define int long long
#define dim 100006
using namespace std;
ifstream fin ("xormax.in");
ofstream fout("xormax.out");
int v[dim],p[25],ind,xo,x;
struct trie
{
int last=0;
trie *kids[2];
trie ()
{
for (int i=0; i<2; i++)
kids[i]=nullptr;
}
};
trie* insert (trie *node,int index)
{
if (node==nullptr)
node=new trie;
if (index<21)
{
int bit=0;
if ((x&p[20-index])!=0)
bit=1;
node->kids[bit]=insert(node->kids[bit],index+1);
}
else node->last=ind;
return node;
}
int bestpref(trie *node,int index)
{
if (index==21)
return node->last;
else
{
int bit=0;
if ((x&p[20-index])!=0)
bit=1;
//if (node->kids[bit]!=nullptr)
bit=1-bit;
if (node->kids[bit]!=nullptr)
{
xo=xo^p[20-index]*bit;
return bestpref(node->kids[bit],index+1);
}
else
{
bit=1-bit;
xo=xo^p[20-index]*bit;
return bestpref(node->kids[bit],index+1);
}
}
}
int32_t main()
{
int n,i,j,solst,soldr,maxi=-1;
fin>>n;
for (i=1; i<=n; i++)
{
fin>>v[i];
v[i]=(v[i]^v[i-1]);
}
p[0]=1;
for (i=1; i<=20; i++)
p[i]=2*p[i-1];
trie *root=nullptr;
root=insert(root,0);
for (i=1; i<=n; i++)
{
x=v[i];
xo=v[i];
j=bestpref(root,0);
if (xo>maxi)
{
maxi=xo;
solst=j,soldr=i;
}
ind=i;
root=insert(root,0);
}
fout<<maxi<<' '<<solst+1<<' '<<soldr<<'\n';
return 0;
}