Pagini recente » Cod sursa (job #2927916) | Cod sursa (job #2901509) | Cod sursa (job #3219881) | Cod sursa (job #1975157) | Cod sursa (job #733923)
Cod sursa(job #733923)
#include<stdio.h>
#define MAXBIT 21
#define NMAX 100005
int val_xor[NMAX],n;
int best = -1,ind1,ind2;
struct trie
{
int pozitie;
trie *directie[2];
trie() { directie[0] = directie[1] = 0; };
};
trie *radacina;
void insert(int val,int indice_bit, trie *nod, int poz)
{
if(indice_bit < 0)
{
nod->pozitie = poz;
return ;
}
int bit = ((val & (1 << indice_bit)) == 0 ? 0 : 1);
if(!nod->directie[bit])
nod->directie[bit] = new trie();
insert(val,indice_bit - 1, nod->directie[bit], poz);
}
int find_poz(int val,int indice_bit,trie *nod)
{
if(indice_bit < 0)
return nod->pozitie;
int bit = (val & (1 << indice_bit));
bit = 1 - (!bit ? 0 : 1);
if(nod->directie[bit])
return find_poz(val,indice_bit - 1, nod->directie[bit]);
return find_poz(val, indice_bit - 1, nod->directie[!bit]);
}
int main ()
{
int i,val,poz;
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n);
radacina = new trie();
insert(0,MAXBIT,radacina,0);
for(i = 1; i <= n; i++)
{
//printf("ok\n");
scanf("%d",&val);
val_xor[i] = (val_xor[i - 1] ^ val);
poz = find_poz(val_xor[i], MAXBIT, radacina);
//printf("mac\n");
if((val_xor[poz] ^ val_xor[i]) > best)
{
best = val_xor[poz] ^ val_xor[i];
ind1 = poz + 1;
ind2 = i;
}
insert(val_xor[i], MAXBIT, radacina,i);
//printf("bau\n");
}
printf("%d %d %d\n",best,ind1,ind2);
return 0;
}