Pagini recente » Cod sursa (job #3140377) | Cod sursa (job #726394) | Cod sursa (job #208919) | Cod sursa (job #2588048) | Cod sursa (job #20637)
Cod sursa(job #20637)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMAX 100001
#define BMAX 32
long v[NMAX], n, max, imax, zmax;
struct nod {
int end;
nod *next[2];
} *r;
void cit()
{
freopen("xormax.in", "rt", stdin);
long i, x;
scanf("%ld", &n);
v[0] = 0;
for (i = 1; i <= n; i++)
{
scanf("%ld", &x);
v[i] = v[i - 1] ^ x;
}
fclose(stdin);
}
void init(nod *&p)
{
p = NULL;
p = (nod *) malloc(sizeof(nod));
p->end = 0;
p->next[0] = p->next[1] = NULL;
}
void bit(int x, int (&y)[BMAX])
{
int i = 0;
memset(y, 0, BMAX * sizeof(int));
while (x > 0)
{
y[ ++i ] = x % 2;
x /= 2;
}
}
void add(long x)
{
int y[BMAX], i;
nod *p, *q;
bit(x, y);
for (p = r, i = BMAX - 1; i >= 1; i--)
{
if (!p->next[ y[i] ])
{
init(q);
p->next[ y[i] ] = q;
}
p = p->next[ y[i] ];
}
}
void rez()
{
long i;
int y[BMAX], z[BMAX], j, yy, zz, p2;
nod *p;
init(r);
for (i = 1; i <= n; i++)
add(v[i]);
for (i = 1; i <= n; i++)
{
bit(v[i], y);
for (p = r, j = BMAX - 1; j >= 1; p = p->next[yy], j--)
{
yy = y[j] ^ 1;
if (p->next[yy])
z[j] = yy;
else
z[j] = yy = y[j];
}
for (zz = 0, p2 = 1, j = 1; j <= BMAX - 1; p2 *= 2, j++)
zz += z[j] * p2;
if (v[i] ^ zz > max)
{
max = v[i] ^ zz;
imax = i;
zmax = zz;
}
}
}
void afis()
{
freopen("xormax.out", "wt", stdout);
long i;
printf("%ld ", max);
for (i = imax; i >= 0 && zmax != v[i]; i--);
printf("%ld %ld\n", i + 1, imax);
fclose(stdout);
}
int main()
{
cit();
rez();
afis();
return 0;
}