Pagini recente » Cod sursa (job #137815) | Cod sursa (job #2235440) | Cod sursa (job #2741759) | Cod sursa (job #899073) | Cod sursa (job #1282082)
#include <stdio.h>
#include <stdlib.h>
#define MAXD 21
#define MAXFII 2
#define MAXN 100000
#define INF 2000000000
int v[MAXN + 1], lis[MAXN + 1], next[MAXN + 1], dr = 1;
typedef struct NODUL{
int ult;
struct NODUL *fii[MAXFII];
}NOD;
int abs(int x){
return x >= 0 ? x : -x;
}
NOD *add(NOD *p, int x, int pas, int k){
int poz;
if(p == NULL){
p = (NOD*) malloc(sizeof(NOD));
p -> ult = 0;
p -> fii[0] = p -> fii[1] = NULL;
}
if(pas != 0){
poz = (x & (1 << (pas - 1))) >> (pas - 1);
p -> fii[poz] = add(p -> fii[poz], x, pas - 1, k);
}
else{
lis[dr] = k;
next[dr] = p -> ult;
p -> ult = dr;
dr++;
}
return p;
}
int maximul(NOD *p1, NOD *p2, int x, int pas, int k){
if(pas == 0){
int min = INF, poz = p2 -> ult;
while(poz > 0){
if(abs(lis[poz] - k) < min)
min = lis[poz];
poz = next[poz];
}
return min;
}
int poz = (x & (1 << (pas - 1))) >> (pas - 1);;
if(p2 -> fii[!poz] != NULL)
return maximul(p1 -> fii[poz], p2 -> fii[!poz], x, pas - 1, k);
else
return maximul(p1 -> fii[poz], p2 -> fii[poz], x, pas - 1, k);
}
int main(){
FILE *in = fopen("xormax.in", "r");
int n, i;
NOD *r = NULL;
fscanf(in, "%d", &n);
for(i = 1; i <= n; i++){
fscanf(in, "%d", &v[i]);
v[i] ^= v[i - 1];
r = add(r, v[i], MAXD - 1, i);
}
fclose(in);
int start, stop = INF, cel;
for(i = 1; i <= n; i++){
cel = maximul(r, r, v[i], MAXD - 1, i);
if(stop == INF || (stop != INF && (v[stop] ^ v[start - 1]) < (v[i] ^ v[cel]))){
if(cel > i){
if(stop > cel || (stop == cel && start < i)){
stop = cel;
start = i + 1;
}
}
else{
if(stop > i || (stop == cel && start < cel)){
stop = i;
start = cel + 1;
}
}
}
}
FILE *out = fopen("xormax.out", "w");
fprintf(out, "%d %d %d", v[stop] ^ v[start - 1], start, stop);
fclose(out);
return 0;
}