Cod sursa(job #469057)

Utilizator APOCALYPTODragos APOCALYPTO Data 5 iulie 2010 22:54:38
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
using namespace std;

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
struct nod{
    nod *son[2];
    vector<int> sol;
    nod()
    {
        memset(son,0,sizeof(son));
    }

};
struct ptsol{
    int max,start,stop;
    ptsol()
    {max=start=stop=0;
    }
};
ptsol curent,rasp;
typedef  nod* trie;
int N;
long long a[100004],s[100005];
bool sir[100005][23];
trie R=new nod;
void ins(trie &n,int ind,int p)
{   if(p==22)
    {
        n->sol.push_back(ind);
        return;
    }

    if(n->son[sir[ind][p]]==NULL)
    {
      n->son[sir[ind][p]]=new nod;
      ins(n->son[sir[ind][p]],ind,p+1);
    }
}
void make(int p,int count)
{int cif;
   if(count<=21)
   {cif=s[p]%2;
   s[p]/=2;
   make(p,count+1);
   sir[p][21-count+1]=cif;
   }
}
inline void search(trie &n,int ind,int p)
{
    if(p==22)
    {int min=200000;
    for(vector<int>::iterator it=n->sol.begin();it!=n->sol.end();++it)
       min=(min<*it)&&(ind<*it)?min:*it;
    curent.stop=min;
    curent.start=ind;

    }
    if(n->son[sir[ind][p]^1]==0)
            {search(n->son[sir[ind][p]],ind,p+1);
            curent.max=curent.max*2+0;
            }
        else
            {search(n->son[sir[ind][p]^1],ind,p+1);
            curent.max=curent.max*2+1;
            }
}
inline void solve()
{
  for(int i=1;i<=N;i++)
     {make(i,1);

     ins(R,i,1);
     }
  for(int i=1;i<=N;i++)
     {   curent.max=0;
         search(R,i,1);
         if(curent.max>rasp.max)
             {rasp.max=curent.max;
             rasp.stop=curent.stop;
             rasp.start=curent.start;
             }
             else if(curent.max==rasp.max)
                   if(curent.stop<rasp.stop)
                      {rasp.stop=curent.stop;
                      rasp.start=curent.start;
                      }
                      else if(curent.stop==rasp.stop)
                              if(curent.stop-curent.start<rasp.stop-rasp.start)
                                  rasp.start=curent.start;
     }
   cout<<rasp.max<<" "<<rasp.start<<" "<<rasp.stop<<"\n";
}
inline void sumation()
{
    s[1]=a[1];
    for(int i=1;i<=N;i++)
     s[i]=s[i-1]^a[i];
}
inline void cit()
{
    ifstream fin("xormax.in");
     fin>>N;
     for(int i=1;i<=N;i++)
       fin>>a[i];
    fin.close();

}
int main()
{
  cit();

  sumation();

  solve();
   cout<<1;
  return 0;

}