Pagini recente » Cod sursa (job #3261263) | Cod sursa (job #1168059) | Cod sursa (job #2669383) | Cod sursa (job #3280427) | Cod sursa (job #3253717)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("xormax.in");
ofstream fout("xormax.out");
#define dim 2
#define NrBiti 20
struct raspuns
{
int val,start,stop;
};
struct Trie
{
int cnt,poz;
Trie* v[dim];
Trie()
{
cnt=poz=0;
for(int i=0;i<dim;i++)
v[i]=NULL;
}
};
void adauga(Trie *nod,int sum,int poz,int PozBit)
{
if(PozBit==-1)
{
nod->poz=poz;
return ;
}
bool bit=(sum&(1<<PozBit));
if(nod->v[bit]==NULL)
{
nod->v[bit]=new Trie;
}
adauga(nod->v[bit],sum,poz,PozBit-1);
}
int ans;
int query(Trie *nod,int s,int pozBit)
{
if(pozBit==-1)
{
return nod->poz;
}
bool bit=(s&(1<<pozBit));
if(nod->v[1-bit]==NULL) ///Nu am gasit bit opus
{
if(nod->v[bit]!=NULL)
return query(nod->v[bit],s,pozBit-1);
else
return -1;
}
else ///Am gasit
{
ans|=(1<<pozBit);
return query(nod->v[1-bit],s,pozBit-1);
}
}
int main()
{
Trie *root=new Trie;
int n,i,nr,sum;
raspuns maxi,aux;
string s;
fin>>n;
fin>>nr;
adauga(root,nr,1,NrBiti);
sum=maxi.val=nr;
maxi.start=0;
maxi.stop=1;
for(i=2;i<=n;i++)
{
fin>>nr;
sum^=nr;
//cout<<sum<<" ";
ans=0;
aux.start=query(root,sum,NrBiti);
aux.stop=i;
aux.val=ans;
if(maxi.val<aux.val)
{
maxi=aux;
}
else if(maxi.val==aux.val)
{
if(maxi.stop>aux.stop)
{
maxi=aux;
}
else if(maxi.stop==aux.stop && maxi.stop-maxi.start>aux.stop-aux.start)
{
maxi=aux;
}
}
adauga(root,sum,i,NrBiti);
}
fout<<maxi.val<<" "<<maxi.start+1<<" "<<maxi.stop;
return 0;
}