Pagini recente » Istoria paginii utilizator/killeruldin9i | Diferente pentru template/lot-2017 intre reviziile 6 si 3 | Monitorul de evaluare | Rating Andrei Coman (fester) | Cod sursa (job #2014364)
#include <bits/stdc++.h>
const int S = 2;
const int MAX_B = 20;
class Trie {
public:
int poz;
Trie *son[S + 5];
Trie() {
poz = -1;
son[0] = son[1] = NULL;
}
void update(int val, int b, int p) {
if (b == -1) {
poz = std::max(poz, p);
} else {
int bit = (val & (1 << b)) > 0;
if (son[bit] == NULL)
son[bit] = new Trie;
son[bit] -> update(val, b - 1, p);
}
}
std::pair<int, int> query(int val, int b) {
int ans = 0;
Trie* aux;
aux = this;
for (; b >= 0; --b) {
int bit = 1 - ((val & (1 << b)) > 0);
if (aux -> son[bit] == NULL)
bit = 1 - bit;
ans = ans + bit * (1 << b);
aux = aux -> son[bit];
}
std::pair<int, int>sol;
sol = std::make_pair(ans ^ val, aux -> poz);
return sol;
}
};
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int n, s = 0, ans = -1, st, dr;
scanf("%d", &n);
Trie* t;
t = new Trie;
t -> update(0, MAX_B, 1);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
s ^= x;
std::pair<int, int>aux = t -> query(s, MAX_B);
if (aux.first > ans) {
ans = aux.first;
st = aux.second;
dr = i;
}
t -> update(s, MAX_B, i + 1);
}
printf("%d %d %d\n", ans, st, dr);
return 0;
}