Pagini recente » Cod sursa (job #2121470) | Cod sursa (job #1800835) | Cod sursa (job #2162828) | Cod sursa (job #2257146) | Cod sursa (job #2064201)
#include <cstdio>
using namespace std;
FILE *in,*out;
int v[100005];
struct Trie
{
int pos;
Trie* son[2];
};
Trie* root;
void addtrie(Trie* node,int x,int nrbit,int i)
{
if(nrbit < 0)
{
node -> pos = i;
}
else
{
int bitt = (x >> nrbit) & 1;
if(node -> son[bitt] == NULL)
{
node -> son[bitt] = new Trie();
}
addtrie(node -> son[bitt],x,nrbit-1,i);
}
}
int solve(Trie* node,int x,int nrbit)
{
if(nrbit < 0)
{
return node -> pos;
}
else
{
int bitt = 1 - ((x >> nrbit) & 1);
if(node -> son[bitt] != NULL)
return solve(node -> son[bitt],x,nrbit-1);
else
return solve(node -> son[1-bitt],x,nrbit-1);
}
}
int main()
{
in = fopen("xormax.in","r");
out = fopen("xormax.out","w");
int n;
fscanf(in,"%d",&n);
root = new Trie();
addtrie(root,0,21,0);
int maxim = -1,st,dr;
for(int i = 1; i <= n; i ++)
{
fscanf(in,"%d",&v[i]);
v[i] ^= v[i-1];
addtrie(root,v[i],21,i);
int pretender = solve(root,v[i],21);
if((v[i] ^ v[pretender]) > maxim)
{
maxim = (v[i] ^ v[pretender]);
st = pretender+1;
dr = i;
if(st > dr)
st = dr;
}
}
fprintf(out,"%d %d %d",maxim,st,dr);
return 0;
}