Pagini recente » Cod sursa (job #1584786) | Cod sursa (job #1035579) | Cod sursa (job #1304050) | Profil casteurr2 | Cod sursa (job #2807192)
#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;
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)
return bestpref(node->kids[1-s[index]+'0'],index+1);
else
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;
s="000000000000000000000";
root=insert(root,0);
for (i=1; i<=n; i++)
{
s.clear();
int x=v[i];
for (j=20; j>=0; j--)
if ((x&p[j])!=0)
s+="1",x-=p[j];
else s+="0";
j=bestpref(root,0);
if (v[j]^v[i]>maxi)
{
maxi=v[j]^v[i];
solst=j,soldr=i;
}
ind=i;
root=insert(root,0);
}
fout<<maxi<<' '<<solst+1<<' '<<soldr<<'\n';
return 0;
}