Cod sursa(job #469224)

Utilizator APOCALYPTODragos APOCALYPTO Data 6 iulie 2010 23:14:47
Problema Xor Max Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 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];

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(vector<int>::iterator it=n->sol.begin();it!=n->sol.end();++it)
       {min=((min>(*it))&&(ind<(*it)))?*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()
{  //ins(R,0,1);
 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;

}