# Cod sursa(job #2739587)

Utilizator Data 8 aprilie 2021 21:15:20 Xor Max 80 cpp-64 done Arhiva de probleme 1.48 kb
``````//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=-1, 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;
}``````