Cod sursa(job #185426)

Utilizator floringh06Florin Ghesu floringh06 Data 25 aprilie 2008 12:58:16
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define FIN "xormax.in"
#define FOUT "xormax.out"
#define MAX_N 100005

typedef struct NOD
{
        int pz, nv;
        NOD *v[3];
};

int A[MAX_N];
int V[MAX_N];
int N;

NOD *H;      
int BEST, li, lf; // solutie

     void init ()
     {
            H = new (NOD), H->pz = 0, H->nv = 20;
            H->v[0] = H->v[1] = NULL;
     }
     
     void update (NOD *nod, int a, int b)
     {
          int d;
          NOD *p;
          if (nod->nv == -1) nod->pz = b;
             else 
             {
                  if (1 << (nod->nv)&a) d = 1; else d = 0;
                  
                  if (nod->v[d] == NULL)
                  {
                       p = new (NOD);
                       p->nv = nod->nv - 1, p->v[0] = p->v[1] = NULL;
                       p->pz = 0;
                       nod->v[d] = p;
                  }
                  update (nod->v[d], a, b);
             }
     }          
     
     void query (NOD *nod, int a, int b)
     {
          int d;
          if (nod->nv == -1)
                   if (A[nod->pz] ^ A[b] > BEST)
                   {
                                  BEST  = A[nod->pz] ^ A[b];
                                  if (nod->pz != b)
                                     li = nod->pz + 1;
                                  else li = nod->pz;
                                        lf = b;
                   }
          if (nod->nv != -1)
          {
                       if (1 << (nod->nv)&a) d = 0; else d = 1;
                       if (nod->v[d] != NULL) query (nod->v[d], a, b);
                          else query (nod->v[(d + 1)%2], a, b);
          }     
     }

     int main ()
     {
         BEST = -1;
         freopen (FIN, "r", stdin);
         freopen (FOUT, "w", stdout);
         
         init ();
         
         scanf ("%d", &N);
         int i, x;
         
         update (H, 0, -1);
         
         for (i = 1; i <= N; ++i)
         {
                 scanf ("%d", V + i);
                 x = V[i];
                 A[i] = A[i - 1] ^ x;
                 update (H, A[i], i);
                 query (H, A[i], i);
         }
         for (i = 1; i <= N; ++i)
             if (V[i] > BEST) BEST = V[i], li = lf = i;
         printf("%d %d %d\n", BEST, li, lf);
         
         return 0;
     }