Pagini recente » Cod sursa (job #402429) | Cod sursa (job #652871) | Cod sursa (job #2030882) | Cod sursa (job #2821020) | Cod sursa (job #946580)
Cod sursa(job #946580)
#include<cstdio>
using namespace std;
const int NMAX = 100005;
int i,n,A[NMAX],X[NMAX],SOL,L,R;
struct Trie
{
int index;
Trie *Left,*Right;
Trie()
{
index=0;
Left=Right=NULL;
}
};
Trie *Root,*Aux;
void Add(int val,int id)
{
int i;
for(Aux=Root,i=21;i>=0;i--)
{
if((1<<i)&val) // val are bit pe pozitia i
{
if(!Aux->Right) Aux->Right=new Trie;
Aux=Aux->Right;
}
else // val nu are bit pe pozitia i
{
if(!Aux->Left) Aux->Left=new Trie;
Aux=Aux->Left;
}
}
Aux->index=id;
}
void Find_Best(int val,int id)
{
int rez,indice,i;
for(Aux=Root,i=21;i>=0;i--)
{
if((1<<i)&val) // val are bit pe pozitia i si de aceea cautam o solutie fara bit
{
if(Aux->Left) Aux=Aux->Left;
else Aux=Aux->Right;
}
else // val nu are bit pe pozitia i si de aceea cautam o solutie cu bit
{
if(Aux->Right) Aux=Aux->Right;
else Aux=Aux->Left;
}
}
indice=Aux->index;
rez=X[indice]^X[id];
if(rez>SOL)
{
SOL=rez;
L=indice+1;
R=id;
}
}
int main()
{
freopen("xormax.in","r",stdin);
freopen("xormax.out","w",stdout);
scanf("%d",&n); Root=new Trie; Add(0,0);
for(i=1;i<=n;i++)
{
scanf("%d",&A[i]);
X[i]=X[i-1]^A[i];
Find_Best(X[i],i);
Add(X[i],i);
}
printf("%d %d %d\n",SOL,L,R);
return 0;
}