Cod sursa(job #1808478)

Utilizator TincaMateiTinca Matei TincaMatei Data 17 noiembrie 2016 18:51:41
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <cstdio>

const int SIGMA = 2;
const int BIT_MAX = 20;

class Trie {
public:
  int inf;
  Trie* son[SIGMA];
  Trie() {
    inf = 0;
    for(int i = 0; i < SIGMA; ++i)
      son[i] = NULL;
  }
  void add(int x, int bit, int poz) {
    int extr;
    if(bit == -1) {
      if(poz > inf)
        inf = poz;
    } else {
      extr = (x & (1 << bit)) > 0;
      if(son[extr] == NULL)
        son[extr] = new Trie;
      son[extr] -> add(x, bit - 1, poz);
    }
  }
};

int main() {
  int n, s, x, extr, best;
  int max, st, dr;
  Trie *t, *cursor;

  t = new Trie;
  t -> add(0, BIT_MAX - 1, 0);

  FILE *fin = fopen("xormax.in", "r");
  fscanf(fin, "%d", &n);
  s = 0;
  max = st = dr = 0;
  for(int i = 1; i <= n; ++i) {
    fscanf(fin, "%d", &x);
    s = s ^ x;
    cursor = t;
    best = 0;
    for(int i = BIT_MAX - 1; i >= 0; --i) {
      extr = (s & (1 << i)) > 0;
      if(cursor -> son[1 - extr] != NULL) {
        best = (best << 1) | 1;
        cursor = cursor -> son[1 - extr];
      } else {
        best = best << 1;
        cursor = cursor -> son[extr];
      }
    }

    if(best > max) {
      max = best;
      dr = i;
      st = cursor -> inf;
    } else if(best == max) {
      dr = i;
      st = cursor -> inf;
    }
    t -> add(s, BIT_MAX - 1, i);
  }
  fclose(fin);
  FILE *fout = fopen("xormax.out", "w");
  fprintf(fout, "%d %d %d", max, st + 1, dr);
  fclose(fout);
  return 0;
}