Pagini recente » Cod sursa (job #2890976) | Cod sursa (job #304812) | Cod sursa (job #2194955) | Cod sursa (job #189570) | Cod sursa (job #1589580)
#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[24];
int main()
{int n,mx=-1,i,x,j,p,u;
in>>n;
add(root,vc,20,0);
for(i=1;i<=n;i++)
{
in>>x;
xorsum[i]=(xorsum[i-1] ^ x);
for(j=0;j<=20;j++)
{
vc[j]=(xorsum[i]&(1<<j));
}
int ind= qu(root,vc,20);
if((xorsum[i]^xorsum[ind])>mx)
{
mx=(xorsum[i]^xorsum[ind]);
p=ind+1;
u=i;
}
add(root,vc,20,i);
}
out<<mx<<" "<<p<<" "<<u<<'\n';
return 0;
}