Pagini recente » Cod sursa (job #2099316) | Cod sursa (job #204863) | Cod sursa (job #1145520) | Cod sursa (job #948620) | Cod sursa (job #1589560)
#include <bits/stdc++.h>
using namespace std;
ifstream in("xormax.in");
ofstream out("xormax.out");
struct Trie{
Trie *sons[2];
int best;
Trie ()
{
best=-1;
sons[0]=sons[1]=NULL;
}
};
Trie *root=new Trie();
void add(Trie *node, bool v[] ,int i,int ind)
{
if(i<0)
{
if(ind>node->best)
node->best=ind;
return;
}
if(!node->sons[v[i]])
node->sons[v[i]]=new Trie;
add(node->sons[v[i]],v,i-1,ind);
}
int qu(Trie *node, bool v[],int i)
{
if(i<0)
{
return node->best;
}
if(node->sons[!v[i]])
{
return qu(node->sons[!v[i]],v,i-1);
}
else if(node->sons[v[i]])
return qu(node->sons[v[i]],v,i-1);
return -1;
}
int xorsum[100005];
bool vc[23];
int main()
{int n,mx=0,i,x,j,p,u;
in>>n;
add(root,vc,0,0);
for(i=1;i<=n;i++)
{
in>>x;
xorsum[i]=(xorsum[i-1] ^ x);
for(j=0;j<=21;j++)
{
vc[j]=(xorsum[i]&(1<<j));
}
add(root,vc,21,i);
int ind= qu(root,vc,21);
if(xorsum[i]^xorsum[ind]>mx)
{
mx=(xorsum[i]^xorsum[ind]);
p=ind+1;
u=i;
}
}
out<<mx<<" "<<p<<" "<<u<<'\n';
return 0;
}