Pagini recente » Cod sursa (job #975977) | Cod sursa (job #1328398) | Cod sursa (job #2158315) | Cod sursa (job #623873) | Cod sursa (job #1830016)
#include <cstdio>
#include <cstring>
#define MAXN 100001
#define MAXS 23
struct trie{
trie *son[2];
int ind;
trie(){
son[1] = son[0] = 0;
ind = 0;
}
}*root;
int s[MAXS], v[MAXN], pos, xors[MAXN];
void add_trie(trie *aux, int *p)
{
if(*p == -1)
{
aux->ind = pos;
return;
}
if(aux->son[*p] == NULL)
aux->son[*p] = new trie;
add_trie(aux->son[*p], p+1);
}
int biggest_xor(trie *aux, int *p)
{
if(*p == -1)
return aux->ind;
if(*p == 0 && aux->son[1] != NULL)
return biggest_xor(aux->son[1], p+1);
else if(*p == 0) return biggest_xor(aux->son[0], p+1);
if(*p == 1 && aux->son[0] != NULL)
return biggest_xor(aux->son[0], p+1);
else if(*p == 1) return biggest_xor(aux->son[1], p+1);
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
root = new trie;
int k, byte, n, i, myxor, maxl = 1, maxr = 1, maxe = -1, j, left, x;
scanf("%d%d", &n, &v[1]);
myxor = 0;
xors[1] = v[1];
for(i=2; i<=n; ++i)
{
scanf("%d", &v[i]);
if(v[i] > maxe)
maxe = v[i];
}
byte = 20;
while(!(maxe & (1<<byte)) && byte > 0) byte--;
s[byte+1] = -1;
add_trie(root, s);
for(i=1; i<=n; ++i)
{
xors[i] = xors[i-1] ^ v[i];
k = 0;
for(j = byte; j>=0; --j)
if(xors[i] & (1<<j))
s[k++] = 1;
else s[k++] = 0;
s[k] = -1;
left = biggest_xor(root, s);
x = xors[i] ^ xors[left];
if(x > myxor)
{
myxor = x;
maxl = left+1;
maxr = i;
}
pos = i;
add_trie(root, s);
}
printf("%d %d %d", myxor, maxl, maxr);
return 0;
}