Cod sursa(job #1282082)

Utilizator hrazvanHarsan Razvan hrazvan Data 3 decembrie 2014 22:25:49
Problema Xor Max Scor 5
Compilator c Status done
Runda Arhiva de probleme Marime 2 kb
#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;
}