Cod sursa(job #2385197)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 21 martie 2019 18:25:16
Problema Xor Max Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define mp make_pair
#define CHECK(x) if(!(x)) return false;
#define CHECKRET(x, y) if(!(x)) return (y);
#define SKIP(x) if((x)) continue;
typedef pair<int, int> pii;

#ifdef INFOARENA
#define ProblemName "xormax"
#else
#define ProblemName "fis"
#endif

#define InFile ProblemName ".in"
#define OuFile ProblemName ".out"

const int MAXN = 100010;
const int MAXBITS = 25;
int v[MAXN];
int N;

struct solution {
  int x, start, stop;
  solution() { }
  solution(int x, int start, int stop) : x(x), start(start), stop(stop) {}
  bool operator<(const solution other) const {
    if (x != other.x) return x < other.x;
    if (stop != other.stop) return stop < other.stop;
    return stop - start < other.stop - other.start;
  }
  bool operator==(const solution other) const {
    CHECK(x == other.x);
    CHECK(stop == other.stop);
    CHECK(start == other.start);
    return true;
  }
};

struct trie {
  trie *nxt[2];
  int stp;
  trie() {
    memset(nxt, 0, sizeof nxt);
    stp = -2;
  }
  void insert(int x, int bit, int stop) {
    if (bit < 0) {
      if(stp == -2) stp = stop;
      return;
    }
    int tar = (x & (1 << bit)) ? 1 : 0;
    if (nxt[tar] == NULL) nxt[tar] = new trie();
    nxt[tar]->insert(x, bit - 1, stop);
  }
  solution querymax(int with, int bit, int fin) {
    if (bit < 0) return solution(0, stp + 1, fin);
    int tar = (nxt[0] == NULL) ? 1 :
      ((nxt[1] == NULL) ? 0 : ((with & (1 << bit)) ? 0 : 1));
    solution aux = nxt[tar]->querymax(with, bit - 1, fin);
    aux.x += (tar << bit);
    return aux;
  }
};

solution brute() {
  solution best(0, -1, -1);
  for (int i = 0; i < N; ++i) {
    int x = 0;
    for (int j = i; j < N; ++j) {
      x ^= v[j];
      best = max(best, solution(x, i, j));
    }
  }
  return best;
}

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  trie *T = new trie();
  scanf("%d", &N);
  solution best(0, -1, -1);
  T->insert(0, MAXBITS - 1, -1);
  int pref = 0;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &v[i]);
    pref ^= v[i];
    T->insert(pref, MAXBITS - 1, i);
    solution cand = T->querymax(pref, MAXBITS - 1, i);
    cand.x ^= pref;
    best = max(best, cand);
  }
  //printf("%d %d %d\n", best.x, best.start + 1, best.stop + 1);

  solution check = brute();
  printf("%d %d %d\n", check.x, check.start + 1, check.stop + 1);
  //fflush(stdout);
  //assert(best == check);

  return 0;
}