Pagini recente » Cod sursa (job #1465899) | Cod sursa (job #1694910) | Cod sursa (job #2622736) | Cod sursa (job #1675573) | Cod sursa (job #2807204)
#include <bits/stdc++.h>
#define int long long
#define dim 100006
#define mod 666013//1000000007
using namespace std;
ifstream fin ("xormax.in");
ofstream fout("xormax.out");
int v[dim],p[25],ind,xo;
string s;
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)
node->kids[s[index]-'0']=insert(node->kids[s[index]-'0'],index+1);
else node->last=ind;
return node;
}
int bestpref(trie *node,int index)
{
if (index==21)
return node->last;
else
{
if (node->kids[1-s[index]+'0']!=nullptr)
{
xo=xo^p[20-index]*(1-s[index]+'0');
return bestpref(node->kids[1-s[index]+'0'],index+1);
}
else
{
xo=xo^p[20-index]*(s[index]-'0');
return bestpref(node->kids[s[index]-'0'],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;
for (i=1; i<=n; i++)
{
s.clear();
xo=v[i];
for (j=20; j>=0; j--)
if ((v[i]&p[j])!=0)
s+="1",v[i]-=p[j];
else s+="0";
if (i>1)
j=bestpref(root,0);
else j=0,xo=0;
if (xo>maxi)
{
maxi=xo;
solst=j,soldr=i;
}
ind=i;
root=insert(root,0);
}
fout<<maxi<<' '<<solst+1<<' '<<soldr<<'\n';
return 0;
}