Pagini recente » Cod sursa (job #409144) | Cod sursa (job #254300) | Cod sursa (job #129654) | Cod sursa (job #1696482) | Cod sursa (job #819)
Cod sursa(job #819)
#include <stdio.h>
#define NMAX 100001
struct Nod
{
int inf;
int ind;
Nod* urm[2];
};
typedef Nod* PNod;
int N;
int nr, x[NMAX];
int max, put_max, start, stop;
PNod R;
using namespace std;
// creez arbore binar cu put_max noduri cu val bitului 0 (numai fii stanga)
void init()
{
PNod p,nou;
p = new Nod;
p->ind = 0;
p->urm[0] = NULL;
p->urm[1] = NULL;
R = p;
for (int i = 0; i<put_max; ++i)
{
nou = new Nod;
nou->ind = 0;
nou->urm[0] = NULL;
nou->urm[1] = NULL;
p->urm[0] = nou;
p = nou;
}
}
// caut in arbore un drum egal cu complementul lui x, adica un xor cat mai mare
void query(int x, int ind)
{
PNod p = R;
int mask = 1 << (put_max-1);
int bit, res = 0, st = 0;
for (int i = put_max-1; i>=0; --i)
{
st = p->ind;
bit = (x&mask)>>i;
bit ^= 1;
if (p->urm[bit])
res+=mask;
else
bit ^= 1;
p = p->urm[bit];
mask >>=1;
}
if (res>max)
{
max = res;
start = st+1;
stop = ind;
}
}
// bag in arbore drumu lui x ca sa pot xora mai tarziu cu altii
void update(int x, int ind)
{
PNod p = R;
int mask = 1 << (put_max-1);
int bit;
for (int i = put_max-1; i>=0; --i)
{
p->ind = ind;
bit = (x&mask)>>i;
if (!(p->urm[bit]))
{
PNod nou = new Nod;
nou->ind = ind;
nou->urm[0] = NULL;
nou->urm[1] = NULL;
p->urm[bit] = nou;
}
p = p->urm[bit];
mask >>= 1;
}
}
int main()
{
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
scanf("%d", &N);
scanf("%d", &x[0]);
max = -1;
put_max = 0;
for (int i = 1; i<N; ++i)
{
scanf("%d", &nr);
x[i] = x[i-1]^nr;
while (nr>=1 << put_max)
++put_max;
}
init();
for (int i = 0; i<N; ++i)
{
query(x[i], i+1);
update(x[i], i+1);
}
printf("%d %d %d", max, start, stop);
return 0;
}