Pagini recente » Cod sursa (job #694289) | Cod sursa (job #644629) | Cod sursa (job #2209045) | Cod sursa (job #1792732) | Cod sursa (job #1492129)
#include<fstream>
#include<vector>
using namespace std;
struct nod
{
bool fr;
size_t zero,unu,val;
vector<size_t> poz;
};
vector<nod> noduri;
vector<size_t> st,dr;
void rez(size_t zero, size_t unu)
{
bool ok=0;
vector<size_t> z,u;
if(!noduri[zero].fr&&!noduri[unu].fr)
{
st.push_back(unu);
dr.push_back(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);
noduri[poz].zero=noduri.size()-1;
noduri[noduri.size()-1].unu=0;
noduri[noduri.size()-1].zero=0;
noduri[poz].fr=true;
poz=noduri[poz].zero;
}
noduri[poz].poz.push_back(0);
noduri[poz].val=0;
noduri[poz].fr=false;
in>>n;
for(i=1;i<=n;i++)
{
in>>x;
y^=x;
x=y;
j=0;
poz=0;
while(x>>j) j++;
for(k=21;k>0;k--)
{
if(x&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;
noduri[noduri.size()-1].fr=true;
}
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;
noduri[noduri.size()-1].fr=true;
}
poz=noduri[poz].zero;
}
}
noduri[poz].poz.push_back(i);
noduri[poz].val=x;
noduri[poz].fr=false;
}
rez(0,0);
for(i=0;i<st.size();i++)
{
if(max<(noduri[st[i]].val^noduri[dr[i]].val))
{
max=noduri[st[i]].val^noduri[dr[i]].val;
st.erase(st.begin(),st.begin()+i);
dr.erase(dr.begin(),dr.begin()+i);
i=0;
}
if(max>(noduri[st[i]].val^noduri[dr[i]].val))
{
st.erase(st.begin()+i);
dr.erase(dr.begin()+i);
i--;
}
}
out<<max<<' ';
nod s,d;
size_t start=0,stop=1,min1=n,min2=n;
if (start>stop)
{
start^=stop;
stop^=start;
start^=stop;
}
for(k=0;k<st.size()&&k<dr.size();k++)
{
s=noduri[st[k]];
d=noduri[dr[k]];
for(i=0;i<s.poz.size();i++)
{
if(s.poz[i]<min1) min1=s.poz[i];
}
for(i=0;i<d.poz.size();i++)
{
if(d.poz[i]<min2) min2=d.poz[i];
}
if(min1<min2)
{
stop=min2;
for(i=1;i<s.poz.size();i++)
{
if(s.poz[i]>min1&&s.poz[i]<min2) min1=s.poz[i];
}
start=min1+1;
}
else
{
stop=min1;
for(i=1;i<d.poz.size();i++)
{
if(d.poz[i]>min2&&d.poz[i]<min1) min2=d.poz[i];
}
start=min2+1;
}
}
out<<start<<' '<<stop;
}