Cod sursa(job #1492129)

Utilizator nickulNic Kul nickul Data 27 septembrie 2015 04:25:02
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.31 kb
#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;
}