Cod sursa(job #2074776)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 24 noiembrie 2017 23:43:58
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>

const int MAXN = 1e5;
#define lim (1 << 21)

struct trie {
  int pos;
  trie *son[2];
  trie() {
    pos = 0;
    son[0] = son[1] = 0;
  }
};

trie *t = new trie;
int v[MAXN + 1];

void add(trie *node, int p, int x) {
  if (!x) {
    node->pos = p;
    return;
  }
  if (!(node->son[(v[p] & x) > 0])) {
    node->son[(v[p] & x) > 0] = new trie;
  }
  add(node->son[(v[p] & x) > 0], p, x >> 1);
}  

int maxxor(trie *node, int p, int x) {
  if (!x) {
    return node->pos;
  }
  if (node->son[!((v[p] & x) > 0)]) {
    return maxxor(node->son[!((v[p] & x) > 0)], p, x >> 1);
  }        
  return maxxor(node->son[(v[p] & x) > 0], p, x >> 1);
}

int main() {
  int n, st, dr, max, x;
  FILE * f = fopen("xormax.in", "r");
  fscanf(f, "%d", &n);
  add(t, 0, lim);
  max = st = dr = 0;
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d", &v[i]);
    v[i] ^= v[i - 1];
    x = maxxor(t, i, lim);
    if (max < v[i] ^ v[x]) {
      max = v[i] ^ v[x];
      dr = i;
      st = x + 1;
    }
    add(t, i, lim);
  }
  fclose(f);
  f = fopen("xormax.out", "w");
  fprintf(f, "%d %d %d\n", max, st, dr);
  fclose(f);
}