Cod sursa(job #789059)

Utilizator visanrVisan Radu visanr Data 16 septembrie 2012 17:14:13
Problema Xor Max Scor 15
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

struct Trie
{
       int pos;
       Trie *fiu[2];
       Trie()
       {
             memset(fiu, 0, sizeof(fiu));
             pos = 0;
       }
};
Trie *T = new Trie;


int N, ans = -1, left, right, now, sol, xorSum, V;


void Insert(Trie *nod, int val, int exp)
{
     if(exp == 0)
     {
            nod -> pos = now;
            return ;
     }
     int X = (val & (1 << exp)) > 0;
     if(nod -> fiu[X] == 0)
            nod -> fiu[X] = new Trie;
     Insert(nod -> fiu[X], val, exp - 1);
}

void Search(Trie *nod, int val, int exp)
{
     if(exp == 0)
     {
            now = nod -> pos;
            return ;
     }
     int X = (val & (1 << exp)) > 0;
     if(X == 0)
     {
          if(nod -> fiu[1])
                 sol |= (1 << exp), Search(nod -> fiu[1], val, exp - 1);
          else
              Search(nod -> fiu[0], val, exp - 1);
     }else
     {
          if(nod -> fiu[1])
                 sol |= (1 << exp), Search(nod -> fiu[1], val, exp - 1);
          else
              Search(nod -> fiu[0], val, exp - 1);
     }
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%i", &N);
    now = 0;
    Insert(T, 0, 21);
    for(int i = 1; i <= N; i++)
    {
          scanf("%i", &V);
          xorSum ^= V;
          sol = now = 0;
          Search(T, xorSum, 21);
          if((xorSum ^ sol) > ans)
                     ans = (xorSum ^ sol), left = now, right = i;
          now = i;
          Insert(T, xorSum, 21);
    }
    printf("%i %i %i\n", ans, left + 1, right);
    return 0;
}