Cod sursa(job #1703577)

Utilizator stoianmihailStoian Mihail stoianmihail Data 17 mai 2016 10:30:42
Problema Xor Max Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <stdio.h>
#include <ctype.h>

#define MAX_BIT 20
#define Nadejde 100000 * (MAX_BIT + 1)
#define Dragoste 4096
#define NIL -1

typedef struct {
  int son, pos;
} pair;

int N, ptr, curr, found;
pair trie[2][Nadejde + 1];

char buff[Dragoste];
int last = Dragoste;

char getChar(FILE *f) {
  if (last == Dragoste) {
    fread(buff, 1, Dragoste, f);
    last = 0;
  }
  return buff[last++];
}

void fscanf(FILE *f, const char *arg, int *result) {
  *result = 0;
  char c;

  do {
    c = getChar(f);
  } while (!isdigit(c));
  do {
    (*result) = (*result << 3) + (*result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
}

/** Initializeaza trie-ul. **/
void init() {
  ptr = 1;
  trie[0][0].son = trie[1][0].son = NIL;
}

/** Parcurge trie-ul, alocand si zonele inca nealocate. **/
void insert(int x, int pos) {
  int i, bit, nod = 0;

  for (i = MAX_BIT; i >= 0; i--) {
    bit = (x >> i) & 1;
    if (trie[bit][nod].son == NIL) {
      trie[0][ptr].son = trie[1][ptr].son = NIL;
      trie[bit][nod].son = ptr;
      ptr++;
    }
    nod = trie[bit][nod].son;
  }
  trie[nod & 1][nod].pos = pos;
}

/** Parcurge trie-ul, obtinand xor-ul maxim cu valoarea "x". **/
void query(int x) {
  int i, bit, nod = 0;
  curr = 0;

  for (i = MAX_BIT; i >= 0; i--) {
    bit = (x >> i) & 1;
    if (trie[!bit][nod].son != NIL) {
      nod = trie[!bit][nod].son;
      curr |= (!bit) << i;
    } else {
      nod = trie[bit][nod].son;
      curr |= bit << i;
    }
  }
  curr ^= x;
  found = trie[nod & 1][nod].pos;
}

int main(void) {
  int i, val, sum = 0, start, stop, max = 0;
  FILE *f = fopen("xormax.in", "r");

  /* Initializarea datelor. */
  init();

  /* Citirea datelor. */
  fscanf(f, "%d", &N);
  insert(sum, 0);
  for (i = 1; i <= N; i++) {
    fscanf(f, "%d", &val);
    sum ^= val;
    query(sum);
    if (curr > max) {
      max = curr;
      start = found;
      stop = i;
    }
    insert(sum, i);
  }
  fclose(f);

  /* Afisarea solutiei. */
  freopen("xormax.out", "w", stdout);
  fprintf(stdout, "%d %d %d\n", max, start + 1, stop);
  fclose(stdout);

  /// Multumim Doamne!
  puts("Doamne ajuta!");
  return 0;
}