Pagini recente » Cod sursa (job #2935215) | Cod sursa (job #1131177) | Cod sursa (job #2518716) | Cod sursa (job #137474) | Cod sursa (job #2342585)
#include <bits/stdc++.h>
#define MAXBITS 22
#define MAXN 100005
int N, XOR[MAXN];
int NTrie = 1, Trie[MAXBITS*MAXN][2];
int TrieIndex[MAXBITS*MAXN];
void Add(int X, int Index) {
for (int i=MAXBITS-1, idx=1, bit; i>=0; --i) {
bit = ((X&(1<<i)) ? 1 : 0);
if (Trie[idx][bit])
idx = Trie[idx][bit];
else
idx = Trie[idx][bit] = ++NTrie;
TrieIndex[idx] = Index;
}
}
int GreedyIndex;
int GreedyFind(int X) {
int output = 0;
for (int i=MAXBITS-1, idx=1, bit; i>=0; --i) {
bit = ((X&(1<<i)) ? 0 : 1);
if (Trie[idx][bit])
idx = Trie[idx][bit],
output += (bit << i);
else if (Trie[idx][1-bit])
idx = Trie[idx][1-bit],
output += ((1-bit)<<i);
GreedyIndex = TrieIndex[idx];
} return output;
}
std::ifstream In ("xormax.in");
std::ofstream Out("xormax.out");
void Citire() {
In >> N;
for (int i=1, X; i<=N; ++i)
In >> X, XOR[i] = XOR[i-1] ^ X;
}
void Rezolvare() {
int Best = 0, A, B;
Add(0, 0);
for (int i=1, X; i<=N; ++i) {
X = GreedyFind(XOR[i]);
if ((XOR[i]^X) > Best)
Best = (XOR[i]^X),
A = GreedyIndex+1, B = i;
Add(XOR[i], i);
} Out << Best << ' ' << A << ' ' << B << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}