Pagini recente » Cod sursa (job #739935) | Cod sursa (job #1632587) | Cod sursa (job #1889796) | Cod sursa (job #788319) | Cod sursa (job #661787)
Cod sursa(job #661787)
#include<fstream>
using namespace std;
int n,v[100010],sumaxor[100010],sol=-1,st,dr,lim=22;
struct Trie
{
Trie *st,*dr;
int poz;
Trie()
{
poz=0;
st=dr=0;
}
};
Trie *T=new Trie;
inline int Search(Trie *nod,int x)
{
int i,bit;
for(i=lim;i>=0;i--)
{
bit=(x & (1<<i));
if(bit) //bitul=1 , deci merg in nodul cu bitul 0 ca sa maximizez suma xor
{
if(nod->dr!=0)
nod=nod->dr;
else
nod=nod->st;
}
else //bitul=0 , deci merg in nodul cu bitul 1 ca sa maximizez suma xor
{
if(nod->st!=0)
nod=nod->st;
else
nod=nod->dr;
}
}
return nod->poz; //returnez indicele elementului gasit
}
inline void Push(Trie *nod,int x,int poz)
{
int i,bit;
for(i=lim;i>=0;i--)
{
bit=(x & (1<<i));
if(bit) //bitul=1 , deci merg in nodul cu bitul 1
{
if(nod->st==0)
nod->st=new Trie;
nod=nod->st;
}
else //bitul=1 , deci merg in nodul cu bitul 1
{
if(nod->dr==0)
nod->dr=new Trie;
nod=nod->dr;
}
}
nod->poz=poz; //am ajuns la pozitia corecta si inserez indicele elementului
}
int main()
{
int i,j;
ifstream fin("xormax.in");
fin>>n;
Push(T,0,0);
for(i=1;i<=n;i++)
{
fin>>v[i];
sumaxor[i]=(sumaxor[i-1]^v[i]);
j=Search(T,sumaxor[i]); //caut j<i astfel incat suma xor de la j+1 la i sa fie maxima
if(sol<(sumaxor[j]^sumaxor[i])) //actualizez maximul
{
sol=(sumaxor[j]^sumaxor[i]);
st=j;
dr=i;
}
Push(T,sumaxor[i],i); //introduc noua suma partiala in Trie
}
fin.close();
ofstream fout("xormax.out");
fout<<sol<<' '<<(st+1)<<' '<<dr<<"\n";
fout.close();
return 0;
}