Pagini recente » Cod sursa (job #837604) | Cod sursa (job #707880) | Cod sursa (job #1338524) | Cod sursa (job #3253549) | Cod sursa (job #2385300)
#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 MAXBUF = 30000000;
char parseBuf[MAXBUF];
char *head;
bool isDigit[255];
void parseInit() {
int a = fread(parseBuf, 1, MAXBUF, stdin);
parseBuf[a] = 0;
head = parseBuf;
memset(isDigit, 0, sizeof isDigit);
for (int i = '0'; i <= '9'; ++i)
isDigit[i] = true;
}
int nextInt() {
int ans = 0;
for (; !isDigit[*head]; ++head);
for (; isDigit[*head]; ++head)
ans = ans * 10 + (*head) - '0';
return ans;
}
const int MAXN = 100010;
const int MAXBITS = 21;
int N;
int solx = 0xF0000000, sols = -1, solstop = -1;
int auxx, auxs;
struct trie {
trie *nxt[2];
int stp;
void insert(int x, int bit, int stop);
void querymax(int with, int bit, int fin);
} phys[MAXN * MAXBITS / 3];
int nxtNode = 0;
void trie::insert(int x, int bit, int stop) {
trie *t = this;
for (; bit >= 0; --bit) {
int tar = (x & (1 << bit)) ? 1 : 0;
if (t->nxt[tar] == NULL) t->nxt[tar] = &phys[nxtNode++];
t = t->nxt[tar];
}
t->stp = stop;
}
void trie::querymax(int with, int bit, int fin) {
trie *t = this;
for (; bit >= 0; --bit) {
int tar = (t->nxt[0] == NULL) ? 1 :
((t->nxt[1] == NULL) ? 0 : ((with & (1 << bit)) ? 0 : 1));
auxx ^= (tar << bit);
int suffixMask = ~((1 << bit) - 1);
if (
((auxx & suffixMask) < (solx & suffixMask))
) return;
t = t->nxt[tar];
}
auxs = t->stp + 1;
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OuFile, "w", stdout));
parseInit();
trie *T = &phys[nxtNode++];
N = nextInt();
T->insert(0, MAXBITS - 1, -1);
int pref = 0;
for (int i = 0; i < N; ++i) {
int x = nextInt();
pref ^= x;
auxx = pref;
T->querymax(pref, MAXBITS - 1, i);
T->insert(pref, MAXBITS - 1, i);
SKIP(auxx <= solx);
solx = auxx, sols = auxs, solstop = i;
}
printf("%d %d %d\n", solx, sols + 1, solstop + 1);
return 0;
}