Pagini recente » ioi_2020 | Cod sursa (job #2357244) | Cod sursa (job #75026) | Cod sursa (job #2962444) | Cod sursa (job #750)
Cod sursa(job #750)
#include <stdio.h>
#define NMAX 100001
#define HMAX 21
struct Nod
{
int inf;
int ind;
Nod* urm[2];
};
typedef Nod* PNod;
int N;
int A[NMAX], 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 - bit;
if (p->urm[bit] != NULL)
res+=mask;
else
bit = 1 - bit;
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", &A[0]);
x[0] = A[0];
max = -1;
put_max = 0;
for (int i = 1; i<N; ++i)
{
scanf("%d", &A[i]);
x[i] = x[i-1]^A[i];
while (A[i]>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;
}