Pagini recente » Cod sursa (job #2040923) | Cod sursa (job #2663113) | Cod sursa (job #182532) | Cod sursa (job #2082514) | Cod sursa (job #2385215)
#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 = 22;
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;
void insert(int x, int bit, int stop);
solution querymax(int with, int bit, int fin);
} phys[MAXN * MAXBITS];
int nxtNode = 0;
void trie::insert(int x, int bit, int stop) {
if (bit < 0) {
stp = stop;
return;
}
int tar = (x & (1 << bit)) ? 1 : 0;
if (nxt[tar] == NULL) nxt[tar] = &phys[nxtNode++];
nxt[tar]->insert(x, bit - 1, stop);
}
solution trie::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;
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
memset(phys, 0, sizeof phys);
trie *T = &phys[nxtNode++];
scanf("%d", &N);
solution best(-1, -1, -1);
T->insert(0, MAXBITS - 1, -1);
int pref = 0;
for (int i = 0; i < N; ++i) {
int x;
scanf("%d", &x);
pref ^= x;
solution cand = T->querymax(pref, MAXBITS - 1, i);
T->insert(pref, MAXBITS - 1, i);
cand.x ^= pref;
best = max(best, cand);
}
printf("%d %d %d\n", best.x, best.start + 1, best.stop + 1);
return 0;
}