Cod sursa(job #469875)

Utilizator APOCALYPTODragos APOCALYPTO Data 9 iulie 2010 14:12:04
Problema Xor Max Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
using namespace std;

#include<iostream>
#include<fstream>
#include<string>
#include<vector>
#include<cassert>
ofstream fout("xormax.out");
struct nod{
    nod *son[2];
    vector<int> sol;
    nod()
    {
        memset(son,0,sizeof(son));

    }

};
struct ptsol{
    long long 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][25];
trie R=new nod;
void ins(trie &n,int ind,int p)
{   if(p==24)
    {
        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<=23)
   {cif=s[p]%2;
   s[p]/=2;
   make(p,count+1);
   sir[p][23-count+1]=cif;
   }
}
inline void search(trie &n,int ind,int p)
{
    if(p>=24)
    {int min=200000;
    //cout<<ind<<":";
    for(vector<int>::iterator it=n->sol.begin();it!=n->sol.end();++it)
       {min=((min>(*it))&&(ind<(*it)))?*it:min;
      // cout<<*it<<" ";

       }
    curent.stop=min;
    //cout<<"\n";
    curent.start=ind+1;

    return;
    }
    if(n->son[sir[ind][p]^1]!=0)
            {curent.max=curent.max*2+1;

                search(n->son[(sir[ind][p])^1],ind,p+1);
                return;
            }
        else
           if(n->son[sir[ind][p]]!=0)
            {curent.max=curent.max*2+0;
                search(n->son[(sir[ind][p])],ind,p+1);
              return;
            }
            else return;
}
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;
         if(!(i==3449&&s[i]==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; //*/
     }


}
inline void sumation()
{
    s[1]=a[1];
    for(int i=1;i<=N;i++)
     {s[i]=s[i-1]^a[i];
     //cout<<s[i]<<" ";
     }
    // cout<<"\n";
}
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();
int max=-1;
int maxi;
   for(int i=1;i<=N;i++)
    if(a[i]>max)
    {max=a[i];
    maxi=i;
    }


    rasp.max=max;
    rasp.start=maxi;
    rasp.stop=maxi;

  solve();
  fout<<rasp.max<<" "<<rasp.start<<" "<<rasp.stop<<"\n";
   fout.close();
  return 0;

}