Pagini recente » Cod sursa (job #2969697) | Cod sursa (job #3256175) | Cod sursa (job #2036752) | Cod sursa (job #3246120) | Cod sursa (job #3253707)
#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 ;
}
int bit=(sum&(1<<PozBit));
if(bit>0)
bit=1;
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=1-(s&(1<<pozBit)); ///bit opus
if(nod->v[bit]==NULL) ///Nu am gasit bit opus
{
if(nod->v[1-bit]!=NULL)
return query(nod->v[1-bit],s,pozBit-1);
else
return 0;
}
else ///Am gasit
{
ans|=(1<<pozBit);
return query(nod->v[bit],s,pozBit-1);
}
}
int main()
{
Trie *root=new Trie;
int n,i,nr,sum;
raspuns maxi,aux;
string s;
fin>>n;
sum=maxi.val=0;
for(i=1;i<=n;i++)
{
fin>>nr;
sum^=nr;
//cout<<sum<<" ";
ans=0;
aux.start=query(root,sum,NrBiti);
aux.stop=i;
aux.val=ans^sum;
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;
}