Cod sursa(job #1580277)

Utilizator Mihai9Oniga Mihai Mihai9 Data 25 ianuarie 2016 18:56:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
const int nMaxBit = 20;
int partialXor[100005];
class Trie {
public:
  int p;
  Trie* fii[2];
  Trie() {
    fii[0] = fii[1] = NULL;
    p = 0;
  }
  void insert(int n, int b, int v) {
    if(b < 0)
      p = 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 p;
    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], sum, Max;scanf("%d", &N);
  lambda->insert(0, nMaxBit, 0);
  sum = pos[0] = 0;
  Max = pos[1] = pos[2] = -1;
  for(int i = 1; i <= N; ++ i) {
    scanf("%d", &nr); sum ^= nr;
    partialXor[i] = sum;
    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;
}