Cod sursa(job #271253)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 5 martie 2009 02:35:50
Problema Xor Max Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<cstdio>
#include<math.h>
#include<cstring>
struct NodT {
    NodT *E[4];
    int poz;
    NodT ()
      {
          memset( E, 0, sizeof( E ) );
          poz = 0;
      }
};
int sxor[100002];
int a[100002];
int start;
int st;
int stop;
int maxbiti;
int sir[100];
int l;
int maxL;
int sol;
NodT *trie = new NodT;
int n;
int power(int val)
{
    int prod = 1;
    while (val) prod *= 2,val--;
    return prod;
}
void insert(NodT *u, int i,int p)
{

    if (i <= 0)  { u -> poz = p; return; }
    if (u -> E[sir[i] + 1] == 0)
    u -> E[sir[i] + 1] =  new NodT;
    insert(u -> E[sir[i] + 1], i - 1, p);

}
void query(NodT *u, int i)
{
    if (i <= 0) {st = u -> poz; return;}
    if (u -> E[2 - sir[i]])
     {
         maxL += power(i-1);
         query(u -> E[2 - sir[i]], i - 1);
     }
     else
      if (u -> E[sir[i] + 1])
       query(u -> E[sir[i] + 1], i - 1);
}

int init()
{

         int aux = sxor[1];
         sir[0] = 0;
         while (aux)
          {
              sir[++sir[0]] = aux % 2;
              aux /= 2;
          }
        insert(trie, maxbiti, 1);
}
int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sxor[i] = sxor[i-1] ^ a[i];
    }

    maxbiti = 23;
    sol = a[1];
    start = 0;
    stop = 1;
    init();

    for(l = 2; l <= n; l++)
     {
         int aux = sxor[l];
         sir[0] = 0;
         while (aux)
          {
              sir[++sir[0]] = aux % 2;
              aux /= 2;
          }
         maxL = 0;
         query(trie,maxbiti);
         if (maxL > sol)
          {
              sol = maxL;
              start = st;
              stop = l;
          }

         insert(trie, maxbiti, l);
         memset(sir,0,sizeof(sir));

     }

    printf("%d %d %d\n", sol, start + 1, stop);
    return 0;
}