Pagini recente » Cod sursa (job #577057) | Cod sursa (job #911554) | Cod sursa (job #1663970) | Cod sursa (job #444090) | Cod sursa (job #1569528)
#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;
}