Cod sursa(job #1492140)

Utilizator nickulNic Kul nickul Data 27 septembrie 2015 05:37:04
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.32 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;
            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<<' ';
}