Cod sursa(job #989801)
#include<cstdio>
#include<cstring>
#include<set>
#include<algorithm>
#define NMAX 100000
using namespace std;
int i,len,pos[NMAX+5],xp[NMAX+5];
char s[25];
struct TRIE {
set <int> pos;
TRIE *edges[2];
};
TRIE *init (TRIE *node) {
if(node == NULL)
node = new TRIE;
node->edges[0] = node->edges[1] = NULL;
return node;
}
TRIE *add (TRIE *ver, char *str) {
if(str[0] == NULL)
ver->pos.insert(i);
else {
int ind = str[0] - '0';
if(ver->edges[ind] == NULL)
ver->edges[ind] = init(ver->edges[ind]);
++str;
ver->edges[ind] = add(ver->edges[ind],str);
}
return ver;
}
int cauta (TRIE *ver, char *str) {
if(str[0] == NULL)
return *(ver->pos.begin());
else {
int ind = str[0] - '0';
++str;
if(ver->edges[!ind] == NULL)
return cauta(ver->edges[ind],str);
else
return cauta(ver->edges[!ind],str);
}
}
void b2 (int x, char *str) {
int st,dr,num = -1;
while(x) {
str[++num] = (x & 1) + '0';
x >>= 1;
}
while(num < 20)
str[++num] = '0';
st = 0;
dr = num - 1;
while(st < dr) {
swap(str[st],str[dr]);
st++;
dr--;
}
str[num] = NULL;
}
int main() {
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
char str[22];
int n,x,val,valmax,st,dr;
TRIE *start = NULL;
start = init(start);
scanf("%d",&n);
b2(0,str);
add(start,str);
for(i = 1; i <= n; i++) {
scanf("%d",&x);
xp[i] = xp[i-1] ^ x;
b2(xp[i],str);
pos[i] = cauta(start,str);
add(start,str);
}
valmax = -1;
for(i = 1; i <= n; i++) {
val = xp[i] ^ xp[pos[i]];
if(val > valmax) {
valmax = val;
st = pos[i] + 1;
dr = i;
}
}
printf("%d %d %d\n",valmax,st,dr);
return 0;
}