Cod sursa(job #1515209)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 1 noiembrie 2015 11:58:21
Problema Xor Max Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <algorithm>

using namespace std;

const int kMaxCells = 10000;

int Trie[kMaxCells][2], nxt = 1;
int seqPos[kMaxCells];

inline void emplace(int x, int pos) {
  int node = 0;
  for (register int i = 21; i >= 0; i--) {
    if (Trie[node][(x >> i) & 1] == 0) {
      Trie[node][(x >> i) & 1] = nxt++;
    }
    node = Trie[node][(x >> i) & 1];
  }
  seqPos[node] = pos;
}

inline pair <unsigned, unsigned> getMax(int x) {
  int node = 0, ans = 0;
  for (register int i = 21; i >= 0; i--) {
    if (Trie[node][~(x >> i) & 1] != 0) {
      ans |= (1 << i);
      node = Trie[node][~(x >> i) & 1];
    } else {
      node = Trie[node][(x >> i) & 1];
    }
  }
  return make_pair(ans, seqPos[node]);
}

int main(void) {
  ifstream in("xormax.in");
  ofstream out("xormax.out");
  int n;
  unsigned xorSum = 0, x;
  unsigned CET, posStart, posEnd;
  
  in >> n;
  CET = 0;
  posStart = posEnd = 0;
  emplace(0, 0);
  for (register int i = 0; i < n; i++) {
    in >> x;
    xorSum ^= x;
    pair <unsigned, unsigned> q = getMax(xorSum);
    if (q.first > CET) {
      CET = q.first;
      posStart = q.second;
      posEnd = i;
    }
    emplace(xorSum, i);
  }
  in.close();

  out << CET << ' ' << posStart + 2 << ' ' << posEnd + 1 << '\n';
  out.close();
  return 0;
}