Pagini recente » Cod sursa (job #1999000) | Cod sursa (job #2696705) | Cod sursa (job #2274324) | Cod sursa (job #215157) | Cod sursa (job #1449807)
#include <iostream>
#include <fstream>
using namespace std;
struct Trie{
Trie *l,*r;
int val;
Trie(){
l=r=NULL;
val=0;
}
};
int N,a[100010],nr,ansl,ind; Trie *T=new Trie();
void ins(Trie *nod, int pb){
if (pb<0){
nod->val=ind;
return;
}
if (nr&(1<<pb)){
if (nod->r==NULL)
nod->r=new Trie();
ins(nod->r,pb-1);
return;
}
if (nod->l==NULL) nod->l=new Trie();
ins(nod->l,pb-1);
}
int fndmax(Trie *nod, int pb){
if (pb<0){
ansl=nod->val;
return 0;
}
if (nr&(1<<pb)){
if (nod->l) return fndmax(nod->l,pb-1);
return (1<<pb)+fndmax(nod->r,pb-1);
}
if (nod->r) return (1<<pb)+fndmax(nod->r,pb-1);
return fndmax(nod->l,pb-1);
}
int main(){
ifstream fin("xormax.in");
ofstream fout("xormax.out");
fin >> N;
int i;
for (i=1; i<=N; i++) fin >> a[i];
nr=0;
ind=0;
ins(T,20);
int MAX=0,cr=0,aux,lt,rt;
for (i=1; i<=N; i++){
cr^=a[i];
nr=cr;
aux=cr^fndmax(T,20);
if (aux>MAX){
MAX=aux;
lt=ansl+1;
rt=i;
}
ind=i;
ins(T,20);
}
fout << MAX << " " << lt << " " << rt << "\n";
return 0;
}