Pagini recente » Cod sursa (job #2075557) | Cod sursa (job #1151416) | Cod sursa (job #324275) | Cod sursa (job #295410) | Cod sursa (job #2739585)
//Ilie Dumitru
#include<cstdio>
struct trie
{
int val, begin, end;
trie *next[2];
};
trie* newTrie()
{
trie *t=new trie;
t->begin=1e7;
t->end=-1;
t->val=0;
t->next[0]=t->next[1]=0;
return t;
}
void insert(trie *t, int xor_val, int begin, int end)
{
for(int i=20;i>-1;--i)
{
if(!t->next[(xor_val>>i) & 1])
t->next[(xor_val>>i) & 1]=newTrie();
t=t->next[(xor_val>>i) & 1];
}
t->val=xor_val;
if(end>t->end || (end==t->end && begin>t->begin))
{
t->begin=begin;
t->end=end;
}
}
void query(trie *t, int xor_val, int& max, int& end)
{
bool x;
int i;
for(i=20;i>-1;--i)
{
x=(xor_val>>i) & 1;
if(t->next[!x])
t=t->next[!x];
else
t=t->next[x];
}
max=t->val^xor_val;
end=t->end;
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int N, x, i, xor_val=0, max=0, begin=0, end=0, aux1, aux2;
trie *t=newTrie();
insert(t, 0, 0, 0);
scanf("%d", &N);
for(i=0;i<N;++i)
{
scanf("%d", &x);
xor_val^=x;
insert(t, xor_val, 1, i+1);
query(t, xor_val, aux1, aux2);
if(aux1>max)
{
max=aux1;
begin=aux2+1;
end=i+1;
}
}
fclose(stdin);
printf("%d %d %d", max, begin, end);
fclose(stdout);
return 0;
}