Cod sursa(job #2384667)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 21 martie 2019 00:32:38
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 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 = 3;

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

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  trie *T = new trie();
  int N;
  scanf("%d", &N);
  int best = 0, pref = 0;
  while (N--) {
    int x;
    scanf("%d", &x);
    pref ^= x;
    T->insert(pref, MAXBITS - 1);
    best = max(best, pref ^ T->querymax(pref, MAXBITS - 1));
  }
  printf("%d\n", best);
  return 0;
}