Cod sursa(job #124456)

Utilizator info_arrandrei gigea info_arr Data 19 ianuarie 2008 12:43:51
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <cstdio>
#include <cstring>

using namespace std;

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

int A[MAX_N];
int B[MAX_N];
int bit[MAX_BIT];

int arb[1 << 22];

int N, i;
int best = 0;

    void initiate ()
    {
         int i;
         B[i] = A[i];
         for (i = 2; i <= N; ++i)
             B[i] = B[i - 1]^A[i];
    }

    int dispose (int c)
    {
         int i, j, ret = 0, ok = 0, bitc = 1;
         
         for (i = 15; i >= 0; --i)
             if ((1 << i)&c) bit[i] = 1; else bit[i] = 0;
             
         int nod = 1;
         for (i = 15; i >= 0; --i)
         {
             if (bit[i] == 2) ok = 1;
             if (!ok)
                {
                     if (arb[nod] == 2 && bitc != bit[i]) ret += 1 << i;
                     if (bit[i - 1] == 2) 
                        {
                               nod = nod << 1;
                               ok = 1;
                               continue;
                        }
                     if (arb[nod << 1] > 0) nod <<= 1;
                        else 
                             {
                                 nod = (nod << 1)|1;
                                 bitc = 1 - bitc;
                             }
                }
             else 
                {
                     if (arb[nod] == 2 && bitc != bit[i]) ret += 1 << i;
                     
                     if (!i) continue;
                     
                     if (bit[i - 1])
                        if (arb[nod << 1] > 0) nod <<= 1;
                                else nod = (nod << 1)|1;
                     if (!bit[i - 1])
                        if (arb[(nod << 1)|1] > 0) nod = (nod << 1)|1;
                                else nod <<= 1;          
                }
         }             
         return ret;
   }

    void insert (int c)
    {
         int i, j;
         int ok = 0;
         for (i = 15; i >= 0; --i)
             if ((1 << i)&c) bit[i] = 1; else bit[i] = 0;
         int nod = 1;
         for (i = 15; i >= 0; --i)
         {
             if (bit[i]){
                  arb[nod] = 2;
                  ok = 1;
             }
             if (!bit[i] && ok) arb[nod] = 1;
             
             if (bit[i] && nod == 1) arb[nod] = 2; // am radacina valida
             if (!bit[i] && nod == 1) arb[nod] = 1; 
             
             if (!i)
             {
                    if (bit[i]) arb[nod] = 2;
                       else arb[nod] = 1;
                    continue;
             }
             
             if (bit[i - 1]) nod <<= 1;
                else nod = (nod << 1)|1;
         }    
    }

    void solve (void)
    {
         int i;
         for (i = 1; i <= N; ++i)
         {
             insert (A[i]);
             int x = dispose (A[i]);
             if (A[i]^x > best) best = A[i]^x;
         }
         printf ("%d\n", best);
    }

    int main ()
    {
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d", &N);
        for (i = 1; i <= N; ++i) scanf ("%d", A + i);

        solve ();
        
        return 0;
    }