Pagini recente » Cod sursa (job #419000) | Cod sursa (job #2737774) | Cod sursa (job #3144390) | Cod sursa (job #2927365) | Cod sursa (job #598785)
Cod sursa(job #598785)
#include <cstdio>
#include <utility>
using namespace std;
const int N = (1 << 21) + 3;
int t[N][2], n, trie[N], p[25], dim;
inline int get_edge(int root, int c) {
int i;
return t[root][c] > 0 ? t[root][c] : -1;
}
inline void add(int a, int ind) {
int i, sw, root = 0, next ;
// printf("%d\n", a);
for(i = 20; i >= 0; --i) {
sw = (a & p[i]) > 0;
// printf("%d", sw);
next = get_edge(root, sw);
if(next == -1) {
++dim;
t[root][sw] = dim;
next = dim;
}
root = next;
}
// printf("\n");
trie[root] = ind;
}
inline pair<int, int> find(int a) {
int ok, i, root = 0, suma = 0, sw;
for(i = 20; i >= 0; --i) {
sw = (a & p[i]) > 0;
ok = 0;
if(t[root][!sw]){
suma += p[i];
root = t[root][!sw];
ok = 1;
}
if(!ok)
root = t[root][sw];
}
return make_pair(trie[root], suma);
}
int main() {
freopen("xormax.in", "r", stdin);
freopen("xormax.out", "w", stdout);
int i, j, a, start = 1, stop = 1, max = 0, s = 0;
scanf("%d", &n);
p[0] = 1;
for(i = 1; i <= 23; ++i)
p[i] = p[i - 1] * 2;
for(i = 1; i <= n; ++i) {
scanf("%d", &a);
s ^= a;
pair<int, int> rez;
if(i > 1){
rez = find(s);
if(rez.second > max){
max = rez.second;
start = rez.first + 1;
stop = i;
}
}
else
max = a;
add(s, i);
}
// for(i = 0; i <= dim; ++i)
// printf("%d %d %d\n", t[i][0], t[i][1], trie[i]);
printf("%d %d %d\n", max, start, stop);
return 0;
}