Pagini recente » Cod sursa (job #1163239) | Cod sursa (job #1749364) | Cod sursa (job #2240725) | Cod sursa (job #1322844) | Cod sursa (job #1492145)
#include<fstream>
#include<vector>
#include<map>
using namespace std;
vector<size_t> gol;
struct nod
{
size_t zero,unu;
};
vector<nod> noduri;
struct frunza
{
size_t val;
vector<size_t> poz;
};
map<size_t,frunza> fr;
struct triplet
{
triplet():unu(0),doi(0),trei(0){}
triplet(size_t u, size_t d, size_t t):unu(u),doi(d),trei(t){}
triplet(size_t u, size_t d):unu(u),doi(d),trei(fr[u].val^fr[d].val){}
size_t unu,doi,trei;
};
vector<triplet> sol;
void rez(size_t zero, size_t unu)
{
bool ok=0;
vector<size_t> z,u;
if(fr.count(zero)&&fr.count(unu))
{
sol.push_back(triplet(unu,zero));
return;
}
if(zero==unu)
{
if(noduri[zero].zero)
{
if(noduri[zero].unu)
{
rez(noduri[zero].zero,noduri[zero].unu);
return;
}
rez(noduri[zero].zero,noduri[zero].zero);
return;
}
if(noduri[zero].unu)
{
rez(noduri[zero].unu,noduri[zero].unu);
return;
}
}
if(noduri[zero].zero&&noduri[unu].unu)
{
rez(noduri[zero].zero,noduri[unu].unu);
ok=1;
}
if(noduri[zero].unu&&noduri[unu].zero)
{
rez(noduri[zero].unu,noduri[unu].zero);
ok=1;
}
if(ok) return;
if(noduri[zero].zero&&noduri[unu].zero)
rez(noduri[zero].zero,noduri[unu].zero);
if(noduri[zero].unu&&noduri[unu].unu)
rez(noduri[zero].unu,noduri[unu].unu);
return;
}
ifstream in("xormax.in");
ofstream out("xormax.out");
int main()
{
size_t n,x,y=0,i,j,k,poz=0,max=0;
noduri.resize(1);
noduri[0].zero=0;
noduri[0].unu=0;
for(k=21;k>0;k--)
{
noduri.resize(noduri.size()+1);
poz=noduri[poz].zero=noduri.size()-1;
noduri[noduri.size()-1].unu=0;
noduri[noduri.size()-1].zero=0;
}
fr[21].poz.push_back(0);
fr[21].val=0;
in>>n;
for(i=1;i<=n;i++)
{
in>>x;
y^=x;
j=0;
poz=0;
while(y>>j) j++;
for(k=21;k>0;k--)
{
if(y&1<<(k-1))
{
if(!noduri[poz].unu)
{
noduri.resize(noduri.size()+1);
noduri[poz].unu=noduri.size()-1;
noduri[noduri.size()-1].unu=0;
noduri[noduri.size()-1].zero=0;
}
poz=noduri[poz].unu;
}
else
{
if(!noduri[poz].zero)
{
noduri.resize(noduri.size()+1);
noduri[poz].zero=noduri.size()-1;
noduri[noduri.size()-1].unu=0;
noduri[noduri.size()-1].zero=0;
}
poz=noduri[poz].zero;
}
}
if(fr.count(poz))
{
fr[poz].poz.push_back(i);
}
else
{
frunza f;
f.poz.push_back(i);
f.val=y;
fr.emplace(poz,f);
}
}
rez(0,0);
for(i=0;i<sol.size();i++)
{
if(max<sol[i].trei)
{
max=sol[i].trei;
sol.erase(sol.begin(),sol.begin()+i);
i=0;
}
if(max>sol[i].trei)
{
sol.erase(sol.begin()+i);
i--;
}
}
out<<max<<' ';
size_t start=n,stop=n,min1,min2;
for(k=0;k<sol.size();k++)
{
min1=fr[sol[k].unu].poz[0];
min2=fr[sol[k].doi].poz[0];
max=0;
if (min1>min2)
{
min1^=min2;
min2^=min1;
min1^=min2;
max=1;
}
if(min2<stop)
{
stop=min2;
start=min1;
if(max)
{
for(i=1;i<fr[sol[k].doi].poz.size();i++)
{
if(fr[sol[k].doi].poz[i]>=min2) break;
start=fr[sol[k].doi].poz[i];
}
}
else
{
for(i=1;i<fr[sol[k].unu].poz.size();i++)
{
if(fr[sol[k].unu].poz[i]>=min2) break;
start=fr[sol[k].unu].poz[i];
}
}
}
}
out<<start+1<<' '<<((stop)?stop:stop+1);
}