Pagini recente » Cod sursa (job #86151) | Cod sursa (job #2722889) | Cod sursa (job #802174) | Cod sursa (job #987974) | Cod sursa (job #1774463)
#include<stdio.h>
#define DPTMAX 21
FILE *in, *out;
int maxxo = -1, maxst, maxdr;
struct nod
{
nod *ze = NULL, *un = NULL;
int ord = 3;
};
void baga(int ilbag, int turn, nod *incep) {
int e = 1 << (DPTMAX - 1);
for(int i = DPTMAX; i > 0; i--) {
if(e > ilbag) {
if(incep->ze == NULL) {
incep->ze = new nod;
}
incep = incep->ze;
//printf("0");
} else {
if(incep->un == NULL) {
incep->un = new nod;
}
//printf("1");
incep = incep->un;
ilbag = ilbag - e;
}
e = (e >> 1);
}
//printf("\n");
incep->ord = turn;
}
void findopt(int ilam, nod *start, int tura)
{
int kanker[23], ilfac = 0;
int e = 1 << (DPTMAX - 1);
for(int i = DPTMAX; i > 0; i--) {
if(e > ilam) {
kanker[i] = 0;
} else {
kanker[i] = 1;
ilam -= e;
}
e = (e >> 1);
}
for(int i = DPTMAX; i > 0; i--) {
ilfac = (ilfac << 1);
if(kanker[i] == 0) {
if(start->un != NULL) {
ilfac++;
start = start->un;
} else {
start = start->ze;
}
} else {
if(start->ze != NULL) {
ilfac++;
start = start->ze;
} else {
start = start->un;
}
}
}
if(ilfac > maxxo) {
maxxo = ilfac;
maxst = start->ord + 1;
maxdr = tura;
}
}
int main ()
{
int n;
in = fopen("xormax.in", "r");
out = fopen("xormax.out", "w");
fscanf(in, "%d", &n);
int v[100000];
for(int i = 0; i < n; i++) {
fscanf(in, "%d", &v[i]);
}
nod *start;
start = new nod;
//printf("%d", start->ord);
baga(0, 0, start);
int xortot = 0;
for(int i = 0; i < n; i++) {
xortot = (xortot ^ v[i]);
findopt(xortot, start, i + 1);
baga(xortot, i + 1, start);
}
fprintf(out, "%d %d %d\n", maxxo, maxst, maxdr);
fclose(in);
fclose(out);
return 0;
}