Pagini recente » Cod sursa (job #1007792) | Cod sursa (job #1518784) | Cod sursa (job #1028573) | Cod sursa (job #3183728) | Cod sursa (job #429876)
Cod sursa(job #429876)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define bmax 22
struct trie{
int l;
trie *f[2];
trie(){
f[0]=f[1]=0;
l=0;
};
};
trie* T;
int n,arr[100010],sum[100010],best,bestL,bestR,ans;
void add(trie *T,int bit,int num,int idx){
int x;
x=(num & (1<<bit))>0;
if (!T->f[x]) T->f[x]=new trie;
if (bit==0){
T->f[x]->l=idx;
return ;
}
add(T->f[x],bit-1,num,idx);
}
void ask(trie *T,int bit,int num){
if (!T->f[0] && !T->f[1]){
ans=T->l;
return;
}
int x;
x=(num & (1<<bit))>0;
if (T->f[1-x]){
ask(T->f[1-x],bit-1,num);
}
else ask(T->f[x],bit-1,num);
}
int main(){
//FILE *in=stdin;
//FILE *out=stdout;
FILE *in=fopen("xormax.in","r");
FILE *out=fopen("xormax.out","w");
fscanf(in,"%d",&n);
for (int i=1;i<=n;i++){
fscanf(in,"%d",&arr[i]);
}
T=new trie();
sum[1]=arr[1];
best=sum[1];bestL=0;bestR=1;
add(T,bmax,sum[1],1);
for (int i=1;i<=n;i++){
sum[i]=sum[i-1]^arr[i];
ask(T,bmax,sum[i]);
if ((sum[i]^sum[ans])>best){
best=sum[i]^sum[ans];
bestL=ans;
bestR=i;
}
add(T,bmax,sum[i],i);
}
fprintf(out,"%d %d %d\n",best,bestL+1,bestR);
//system("pause");
return 0;
}