Pagini recente » Cod sursa (job #2843782) | Cod sursa (job #1643690) | Cod sursa (job #2479330) | Cod sursa (job #1992485) | Cod sursa (job #271249)
Cod sursa(job #271249)
#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;
void insert(NodT *u, int i,int p)
{
if (i > 0)
{
if (u -> E[sir[i] + 1] == 0)
{
u -> E[sir[i] + 1] = new NodT;
insert(u -> E[sir[i] + 1], i - 1, p);
}
else
insert(u -> E[sir[i] + 1], i - 1, p);
}
else
u-> poz = p;
}
void query(NodT *u, int i)
{
if (i > 0)
{
if (u -> E[2 - sir[i]])
{
maxL += pow(2, 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);
}
else
st = u -> poz;
}
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];
}
for(l = 1; l <= n; l++)
{
int aux = sxor[l];
sir[0] = 0;
while (aux)
{
sir[++sir[0]] = aux % 2;
aux = aux / 2;
}
if (maxbiti < sir[0]) maxbiti = sir[0];
sir[0] = maxbiti;
for(int j = 1; j <= maxbiti; j++)
sir[j] = 0;
}
for(l = 1; l <= n; l++)
{
int aux = sxor[l];
sir[0] = 0;
while (aux)
{
sir[++sir[0]] = aux % 2;
aux = aux / 2;
}
maxL = 0;
query(trie,maxbiti);
if (maxL > sol)
{
sol = maxL;
start = st;
stop = l;
}
insert(trie, maxbiti, l);
for(int j = 1; j <= maxbiti; j++)
sir[j] = 0;
}
printf("%d %d %d\n", sol, start + 1, stop);
return 0;
}