Pagini recente » Cod sursa (job #1190493) | Cod sursa (job #1347663) | Cod sursa (job #2296464) | Cod sursa (job #281501) | Cod sursa (job #1515209)
#include <fstream>
#include <algorithm>
using namespace std;
const int kMaxCells = 10000;
int Trie[kMaxCells][2], nxt = 1;
int seqPos[kMaxCells];
inline void emplace(int x, int pos) {
int node = 0;
for (register int i = 21; i >= 0; i--) {
if (Trie[node][(x >> i) & 1] == 0) {
Trie[node][(x >> i) & 1] = nxt++;
}
node = Trie[node][(x >> i) & 1];
}
seqPos[node] = pos;
}
inline pair <unsigned, unsigned> getMax(int x) {
int node = 0, ans = 0;
for (register int i = 21; i >= 0; i--) {
if (Trie[node][~(x >> i) & 1] != 0) {
ans |= (1 << i);
node = Trie[node][~(x >> i) & 1];
} else {
node = Trie[node][(x >> i) & 1];
}
}
return make_pair(ans, seqPos[node]);
}
int main(void) {
ifstream in("xormax.in");
ofstream out("xormax.out");
int n;
unsigned xorSum = 0, x;
unsigned CET, posStart, posEnd;
in >> n;
CET = 0;
posStart = posEnd = 0;
emplace(0, 0);
for (register int i = 0; i < n; i++) {
in >> x;
xorSum ^= x;
pair <unsigned, unsigned> q = getMax(xorSum);
if (q.first > CET) {
CET = q.first;
posStart = q.second;
posEnd = i;
}
emplace(xorSum, i);
}
in.close();
out << CET << ' ' << posStart + 2 << ' ' << posEnd + 1 << '\n';
out.close();
return 0;
}