Pagini recente » Cod sursa (job #2135036) | Cod sursa (job #1495138) | Cod sursa (job #1495425) | Cod sursa (job #1995248) | Cod sursa (job #271254)
Cod sursa(job #271254)
#include<cstdio>
#include<math.h>
#include<cstring>
struct NodT {
NodT *E[4];
int poz;
NodT ()
{
memset( E, 0, sizeof( E ) );
poz = 0;
}
};
int sxor[100002];
int a[100002];
int start;
int st;
int stop;
int maxbiti;
int sir[100];
int l;
int maxL;
int sol;
NodT *trie = new NodT;
int n;
int power(int val)
{
int prod = 1;
while (val) prod *= 2,val--;
return prod;
}
void insert(NodT *u, int i,int p)
{
if (i <= 0) { u -> poz = p; return; }
if (u -> E[sir[i] + 1] == 0)
u -> E[sir[i] + 1] = new NodT;
insert(u -> E[sir[i] + 1], i - 1, p);
}
void query(NodT *u, int i)
{
if (i <= 0) {st = u -> poz; return;}
if (u -> E[2 - sir[i]])
{
maxL += power(i-1);
query(u -> E[2 - sir[i]], i - 1);
}
else
if (u -> E[sir[i] + 1])
query(u -> E[sir[i] + 1], i - 1);
}
int init()
{
sol = a[1];
start = 0;
stop = 1;
int aux = sxor[1];
sir[0] = 0;
while (aux)
{
sir[++sir[0]] = aux % 2;
aux /= 2;
}
insert(trie, maxbiti, 1);
memset(sir,0,sizeof(sir));
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sxor[i] = sxor[i-1] ^ a[i];
}
maxbiti = 23;
init();
for(l = 2; l <= n; l++)
{
int aux = sxor[l];
sir[0] = 0;
while (aux)
{
sir[++sir[0]] = aux % 2;
aux /= 2;
}
maxL = 0;
query(trie,maxbiti);
if (maxL > sol)
{
sol = maxL;
start = st;
stop = l;
}
insert(trie, maxbiti, l);
memset(sir,0,sizeof(sir));
}
printf("%d %d %d\n", sol, start + 1, stop);
return 0;
}