Pagini recente » Cod sursa (job #2567790) | Cod sursa (job #2638404) | Cod sursa (job #3221765) | Cod sursa (job #518676) | Cod sursa (job #2394070)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
int n,i,x,v[100010],put,x2,y2,ma,ma2,poz,poz2,poz3,poz4,r,nr[100009];
struct Trie
{
Trie *fii[2];
};
Trie *t=new Trie();
void adauga(Trie *p,int x,int put)
{
if(put==0)
{
return;
}
if(i==1)
{
//g<<x<<" "<<put<<" "<<x/put%2<<'\n';
}
if(p->fii[(x/put)%2]==NULL)
{
p->fii[(x/put)%2]=new Trie();
}
adauga(p->fii[(x/put)%2],x%put,put/2);
}
int cauta(Trie *p,int put,int x)
{
//g<<put<<'\n';
if(put==0)
{
return 0;
}
if(p->fii[(x/put)^1]!=NULL)
{
return put+cauta(p->fii[(x/put)^1],put/2,x%put);
}
else
{
return cauta(p->fii[(x/put)],put/2,x%put);
}
}
int main()
{
f>>n;
for(i=1; i<=n; i++)
{
f>>x;
nr[i]=x;
v[i]=v[i-1]^x;
if(v[i]>ma)
{
ma=v[i];
poz=i;
poz=i;
poz2=i;
}
}
put=1;
for(i=1; i<=21; i++)
{
put*=2;
}/*
for(i=0; i<=n; i++)
{
adauga(t,v[i],put);
}*/
adauga(t,0,put);
for(i=1; i<=n; i++)
{
ma2=cauta(t,put,v[i]);
if(ma<ma2)
{
r=1;
ma=ma2;
poz=v[i];
poz2=v[i]^ma2;
poz4=i;
}
adauga(t,v[i],put);
}
if(r==0)
{
//g<<ma<<" "<<poz<<" "<<poz2;
return 0;
}
//g<<poz<<" "<<poz2<<'\n';
f.close();
//f.open("xormax.in");
//f>>n;
long long xoor=0;
for(i=poz4; i>0; --i)
{
xoor^nr[i];
if (xoor==ma)
{
poz3=i;
break;
}
}
g<<ma<<" "<<poz3<<" "<<poz4;
return 0;
}