Pagini recente » Cod sursa (job #1340607) | Cod sursa (job #2198063) | Cod sursa (job #2300643) | Cod sursa (job #1540675) | Cod sursa (job #2063952)
#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 byte = (x >> nrbit) & 1;
if(node -> son[byte] == NULL)
{
node -> son[byte] = new Trie();
node -> pos = -1;
}
addtrie(node -> son[byte],x,nrbit-1,i);
}
}
int solve(Trie* node,int x,int nrbit)
{
if(nrbit < 0)
{
return node -> pos;
}
else
{
int byte = 1 - ((x >> nrbit) & 1);
if(node -> son[byte] != NULL)
return solve(node -> son[byte],x,nrbit-1);
else
return solve(node -> son[1-byte],x,nrbit-1);
}
}
int main()
{
in = fopen("xormax.in","r");
out = fopen("xormax.out","w");
int n;
fscanf(in,"%d",&n);
root = new Trie();
int maxim = -1,st,dr;
addtrie(root,0,21,0);
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;
}
}
fprintf(out,"%d %d %d",maxim,st,dr);
return 0;
}