Cod sursa(job #271250)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 5 martie 2009 02:18:45
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 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;
void insert(NodT *u, int i,int p)
{

    if (i > 0)
    {
     if (u -> E[sir[i] + 1] == 0)
    {
    u -> E[sir[i] + 1] =  new NodT;
    insert(u -> E[sir[i] + 1], i - 1, p);
    }
    else
     insert(u -> E[sir[i] + 1], i - 1, p);
    }
    else
    u-> poz = p;
}
void query(NodT *u, int i)
{
    if (i > 0)
    {
    if (u -> E[2 - sir[i]])
     {
         maxL += pow(2, 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);
    }
    else
    st = u -> poz;
}


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];
    }
    for(l = 1; l <= n; l++)
    {
        int aux = sxor[l];
         sir[0] = 0;
         while (aux)
          {
              sir[++sir[0]] = aux % 2;
              aux = aux / 2;
          }
         if (maxbiti < sir[0]) maxbiti = sir[0];
         sir[0] = maxbiti;
         memset(sir,0,sizeof(sir));
    }

    for(l = 1; l <= n; l++)
     {
         int aux = sxor[l];
         sir[0] = 0;
         while (aux)
          {
              sir[++sir[0]] = aux % 2;
              aux = 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;
}