Cod sursa(job #469232)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 iulie 2010 23:54:07
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.49 kb
using namespace std;

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

    }

};
struct ptsol{
    unsigned int max,start,stop;
    ptsol()
    {max=start=stop=0;

    }
};
ptsol curent,rasp;
typedef  nod* trie;
int N;
unsigned int a[100100],s[100100];
int it;
bool sir[24];
trie R=new nod;
void ins(trie &n,int ind,int p)
{   if(p>=23)
    {
        n->sol.push_back(ind);
        return;
    }

    if(n->son[sir[p]]==NULL)
    {
      n->son[sir[p]]=new nod;
    }
      ins(n->son[sir[p]],ind,p+1);

}

/*void make(int p,int count)
{int cif;
   if(count<=22)
   {cif=s[p]%2;
   s[p]/=2;
   make(p,count+1);
   sir[p][22-count+1]=cif;
   }
}*/
inline void search(trie &n,int ind,int p)
{
    if(p>=23)
    {int min=200000;
    //cout<<ind<<":";
    for(it=0;it<=n->sol.size()-1;++it)
       {min=((min>(n->sol[it]))&&(ind<(n->sol[it])))?n->sol[it]:min;
      // cout<<*it<<" ";

       }
    curent.stop=min;

    curent.start=ind;

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

                search(n->son[sir[p]],ind,p+1);

            }
        else
            {curent.max=curent.max*2+1;

                search(n->son[(sir[p])^1],ind,p+1);

            }
}
inline void solve()
{ for(int i=1;i<=N;i++)
     {
     bitset<23>muri(s[i]);

     for(int j=0;j<=22;j++)
       {sir[j]=muri[22-j];

       }


     ins(R,i,1);
     }

  for(int i=1;i<=N;i++)
     {   curent.max=0;
        bitset<23>muri(s[i]);

     for(int j=0;j<=22;j++)
       {sir[j]=muri[22-j];

       }
        //ins(R,i,1);
         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;
     }
     for(int i=1;i<=N;i++)
    {curent.max=a[i];
    curent.stop=i;
    curent.start=i;
    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;
     }
   fout<<rasp.max<<" "<<rasp.start+1<<" "<<rasp.stop<<"\n";
}
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();

  solve();
   //cout<<1;
   fout.close();
  return 0;

}