Pagini recente » Cod sursa (job #3222055) | Cod sursa (job #2886794) | Cod sursa (job #3269005) | Cod sursa (job #1320533) | Cod sursa (job #2063980)
#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();
node -> pos = -1;
}
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 maxim,st,dr;
void update(int from, int to) {
int pretender = v[from] ^ v[to];
if(maxim < pretender) {
maxim = pretender;
if(from < to) {
st = from + 1;
dr = to;
}
}
}
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);
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);
update(pretender,i);
}
fprintf(out,"%d %d %d",maxim,st,dr);
return 0;
}