Cod sursa(job #1569528)

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

const int nMaxBit = 20;
const int maxSize = 1 << 20;

class ReadStream {
private:
  int cursor;
  char buf[maxSize];
  FILE *f;
  inline void move() {
    ++ cursor;
    if(cursor == maxSize) {
      cursor = 0;
      fread(buf, maxSize, 1, f);
    }
  }
  inline int todig(char c) {
    return c - '0';
  }

public:
  ReadStream() {}
  ReadStream(const char *fname) {
    f = fopen(fname, "r");
    cursor = 0;
    fread(buf, maxSize, 1, f);
  }

  ReadStream &operator >> (int& N) {
    char sign = '+';
    while(!isdigit(buf[cursor])) {
      sign = buf[cursor];
      move();
    }

    N = 0;
    while(isdigit(buf[cursor])) {
      N = N * 10 + todig(buf[cursor]);
      move();
    }

    if(sign == '-')
      N = -N;
    return *this;
  }

  ReadStream &operator >> (float& N) {
    char sign = '+';
    while(!isdigit(buf[cursor])) {
      sign = buf[cursor];
      move();
    }
    N = 0;
    while(isdigit(buf[cursor])) {
      N = N * 10 + todig(buf[cursor]);
      move();
    }

    if(buf[cursor] == '.') {
      float p = 0.1;
      move();
      while(isdigit(buf[cursor])) {
        N = N + p * todig(buf[cursor]);
        p *= 0.1;
        move();
      }
    }

    if(sign == '-')
      N = -N;
    return *this;
  }
};

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);
  }

};

int partialXor[131072];
Trie* lambda = new Trie();

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

  int N, nr, pos[3];
  in >> N;
  lambda->insert(0, nMaxBit, 0);

  int sum = (pos[0] = 0), Max = (pos[1] = pos[2] = -1);
  for(int i = 1; i <= N; ++ i) {
    in >> 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;
}