Pagini recente » Monitorul de evaluare | Cod sursa (job #84791) | Diferente pentru preoni-2007/runda-3/solutii intre reviziile 16 si 15 | Profil bulgaras | Cod sursa (job #2155940)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct trie{
int poz;
trie *z,*u;
trie(){
poz=0;
z=0;
u=0;
}
};
int v[100010],mx,start,stop,r;
trie *o = new trie;
void add(int x,int p){
trie *nod=o;
for (int i=1<<21;i>0;i>>=1){
if (x&i){
if (nod->u==NULL)
nod->u = new trie;
nod=nod->u;
}
else {
if (nod->z==NULL)
nod->z = new trie;
nod=nod->z;
}
}
nod->poz=p;
}
int check(int x){
trie *nod=o;
int t=0;
for (int i=1<<21;i>0;i>>=1){
if ((!(x&i))&&nod->u){
nod=nod->u;
t+=i;
}
else if ((x&i)&&nod->z){
nod=nod->z;
t+=i;
}
else if (nod->u) nod=nod->u;
else if (nod->z) nod=nod->z;
else break;
}
r=1+nod->poz;
return t;
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
int n,aux;
scanf("%d %d",&n,&v[1]);
mx=v[1];start=1;stop=1;
for (int i=2;i<=n;i++){
scanf("%d",&v[i]);
if (mx<v[i]){
mx=v[i];
start=i;
stop=i;
}
v[i]=v[i-1]^v[i];
if (mx<v[i]){
mx=v[i];
start=1;
stop=i;
}
}
add(v[1],1);
add(v[2],2);
for (int i=3;i<=n;i++){
aux=check(v[i]);
if (aux>mx||(aux==mx&&i>stop)||(aux==mx&&i==stop&&start<r)){
mx=aux;
start=r;
stop=i;
}
add(v[i],i);
}
printf("%d %d %d",mx,start,stop);
return 0;
}