Pagini recente » Cod sursa (job #1187778) | Cod sursa (job #1768316) | Cod sursa (job #319813) | Cod sursa (job #2903730) | Cod sursa (job #1492140)
#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<<' ';
}