Cod sursa(job #1569532)

Utilizator tudorcomanTudor Coman tudorcoman Data 15 ianuarie 2016 17:58:44
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <cstdio>

const int nMaxBit = 20;
int partialXor[131072];
class Trie {
public:
  int pos;
  Trie* fii[2];

  Trie() {
    fii[0] = fii[1] = NULL;
    pos = 0;
  }

  void insert(int n, int b, int v) {
    if(b < 0)
      pos = v;
    else {
      bool x = n & (1 << b);
      if(fii[x] == NULL)
        fii[x] = new Trie();
      fii[x]->insert(n, b - 1, v);
    }
  }

  int query(int n, int b = nMaxBit) {
    if(b < 0)
      return pos;
    bool x = !(n & (1 << b));
    if(fii[x] == NULL)
      x = !x;
    return fii[x]->query(n, b - 1);
  }

} *lambda = new Trie();

int main() {
  freopen("xormax.in", "r", stdin);
  freopen("xormax.out", "w", stdout);

  int N, nr, pos[3];
  scanf("%d", &N);
  lambda->insert(0, nMaxBit, 0);

  int sum = (pos[0] = 0), Max = (pos[1] = pos[2] = -1);
  for(int i = 1; i <= N; ++ i) {
    scanf("%d", &nr);
    partialXor[i] = (sum ^= nr);
    pos[0] = lambda->query(sum);
    if(sum ^ partialXor[pos[0]] > Max) {
      Max = sum ^ partialXor[pos[0]];
      pos[1] = pos[0] + 1;
      pos[2] = i;
    }
    lambda->insert(sum, nMaxBit, i);
  }

  printf("%d %d %d\n", Max, pos[1], pos[2]);
  return 0;
}