Pagini recente » Cod sursa (job #1384996) | Cod sursa (job #36517) | Cod sursa (job #2385778) | Cod sursa (job #601888) | Cod sursa (job #601688)
Cod sursa(job #601688)
#include <iostream>
#include <fstream>
#define NMax 100005
using namespace std;
struct Trie
{
int NS;
Trie *Son[2];
Trie ()
{
NS=-1;
Son[0]=Son[1]=0;
}
};
Trie *T=new Trie;
int N, X[NMax], XorMax[NMax], Start, End, S;
void Read ()
{
ifstream fin ("xormax.in");
fin >> N;
for (int i=1; i<=N; ++i)
{
fin >> X[i];
}
fin.close ();
}
void Print ()
{
ofstream fout ("xormax.out");
fout << S << " " << Start << " " << End << "\n";
fout.close ();
}
void Insert (Trie *Node, int Element, int Bit)
{
if (Bit==-1)
{
Node -> NS=Element;
return;
}
if (((1<<Bit)&Element)!=0)
{
if (Node -> Son[1]==0)
{
Node -> Son[1]=new Trie;
}
Insert (Node -> Son[1], Element, Bit-1);
}
else
{
if (Node -> Son[0]==0)
{
Node -> Son[0]=new Trie;
}
Insert (Node -> Son[0], Element, Bit-1);
}
}
int Query (Trie *Node, int Q, int Bit)
{
if (Bit==-1)
{
return Node-> NS;
}
if ((Q&(1<<Bit))!=0)
{
if (Node -> Son[0]!=0)
{
return Query (Node -> Son[0], Q, Bit-1);
}
return Query (Node -> Son[1], Q, Bit-1);
}
if (Node -> Son[1]!=0)
{
return Query (Node -> Son[1], Q, Bit-1);
}
return Query (Node -> Son[0], Q, Bit-1);
}
int main()
{
int Xor, CurrentXor;
Read ();
XorMax[1]=X[1];
CurrentXor=X[1];
Insert (T, X[1], 21);
for (int i=2; i<=N; ++i)
{
CurrentXor^=X[i];
Xor=Query (T, CurrentXor, 21);
XorMax[i]=max (X[i], CurrentXor^Xor);
Insert (T, CurrentXor, 21);
}
for (int i=1; i<=N; ++i)
{
if (XorMax[i]>S)
{
S=XorMax[i];
End=i;
}
}
Xor=X[End];
Start=End;
for (int i=End-1; i>0 && Xor!=S; --i)
{
Xor^=X[i];
Start=i;
}
Print ();
return 0;
}