Pagini recente » Cod sursa (job #1428731) | Cod sursa (job #712739) | Cod sursa (job #91732) | Cod sursa (job #918892) | Cod sursa (job #1492136)
#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;
poz=noduri[poz].zero;
}
noduri[poz].poz.push_back(0);
noduri[poz].val=0;
noduri[poz].fr=true;
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;
}
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;
}
}
noduri[poz].poz.push_back(i);
noduri[poz].val=x;
noduri[poz].fr=true;
}
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<<' ';
size_t start=n,stop=n,min1,min2;
/*for(k=0;k<st.size()&&k<dr.size();k++)
{
min1=noduri[st[k]].poz[0];
min2=noduri[dr[k]].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<noduri[dr[k]].poz.size();i++)
{
if(noduri[dr[k]].poz[i]>=min2) break;
start=noduri[dr[k]].poz[i];
}
}
else
{
for(i=1;i<noduri[st[k]].poz.size();i++)
{
if(noduri[dr[k]].poz[i]>=min2) break;
start=noduri[dr[k]].poz[i];
}
}
}
}*/
out<<start+1<<' '<<((stop)?stop:stop+1);
}