Pagini recente » Cod sursa (job #436416) | Cod sursa (job #489736) | Cod sursa (job #979440) | Istoria paginii runda/aaaa | Cod sursa (job #1224105)
#include <fstream>
#define NMAX 100005
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int N,Array[NMAX];
int Bit[25];
int start,stop,Max=-1;
struct Trie{
int aparition,position,diam;
Trie* next[2];
Trie()
{
aparition=position=diam=0;
next[0]=next[1]=0;
}
};
Trie* Root=new Trie;
void Read()
{
int i;
f>>N;
for(i=1;i<=N;i++)
f>>Array[i];
}
void Descomp(int x)
{
Bit[0]=0;
while(x!=0)
{
Bit[++Bit[0]]=x%2;
x/=2;
}
Bit[0]=22;
}
void Browse(int poz)
{
Trie *node=Root;
int number=0;
for(int i=Bit[0];i>=1;i--)
{
if(node->next[1-Bit[i]]!=0)
{
number=number*2+1;
node=node->next[1-Bit[i]];
}
else
{
number=number*2;
node=node->next[Bit[i]];
}
}
if(number>Max)
{
Max=number;
stop=poz;
}
}
void insert(Trie* node,int poz)
{
if(poz==0)
return;
if(node->next[Bit[poz]]==0)
node->next[Bit[poz]]=new Trie;
insert(node->next[Bit[poz]],poz-1);
}
void getAnswer()
{
int i,number=Array[1];
Max=Array[1];
stop=1;
Descomp(Array[1]);
insert(Root,Bit[0]);
for(i=2;i<=N;i++)
{
number=(number^Array[i]);
if(Max<number)
{
Max=number;
stop=i;
}
Descomp(number);
Browse(i);
insert(Root,Bit[0]);
}
}
void countBegin()
{
int i=stop,number=Array[stop];
while(i>0 && number!=Max)
{
i--;
number=(Array[i]^number);
}
g<<Max<<" "<<i<<" "<<stop<<"\n";
}
int main()
{
Read();
getAnswer();
countBegin();
return 0;
}