Pagini recente » Atasamentele paginii Clasament eusebiu_oji_2014_cls9 | Istoria paginii runda/antr10/clasament | Cod sursa (job #1894196) | Cod sursa (job #1914302) | Cod sursa (job #1223316)
#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;
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;
}
}
void Browse(int poz)
{
int index=Bit[0],number=0;
Trie* node=(Root->next[1]);
if(Root->diam<=Bit[0])
{
index=Root->diam;
node=Root;
int ind=Bit[0];
while(ind>index)
{
number=number*2+Bit[ind];
--ind;
}
}
else
{
node=Root;
int value=1;
while(node!=0 && node->diam>Bit[0])
{
if((node->next[1])!=0 && (node->next[1])->diam==node->diam-1)
{
node=node->next[1];
value=1;
}
else
{
node=node->next[0];
value=0;
}
number=number*2+value;
}
}
while(index>0)
{
if(node->next[1-Bit[index]]!=0 && (node->next[1-Bit[index]])->diam==node->diam-1)
{
node=node->next[1-Bit[index]];
number=number*2+1;
}
else
{
node=node->next[Bit[index]];
number=number*2;
}
--index;
}
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);
node->diam=max(node->diam,(node->next[Bit[poz]])->diam+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;
}