Cod sursa(job #1450742)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 14 iunie 2015 15:46:16
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <stdio.h>
using namespace std;

const int Dim = 100005;

struct Trie
{
    int Pos;
    Trie *Son[2];

    Trie()
    {
        Pos = 0;
        Son[0] = Son[1] = 0;
    }
};

Trie *T = new Trie();

int N,Ans,Value,i,L,R,Val,Sol = -1;
int X[Dim];

void Add(Trie *Node,int P)
{
    if (P < 0)
    {
        Node->Pos = i;
        return;
    }
    if (Val & (1 << P))
    {
        if (Node->Son[1] == 0)
            Node->Son[1] = new Trie();
        Add(Node->Son[1],P-1);
        return;
    }
    if (Node->Son[0] == 0)
        Node->Son[0] = new Trie();
    Add(Node->Son[0],P-1);
}

int Query(Trie *Node,int P)
{
    if (P < 0)
    {
        Ans = Node->Pos;
        return 0;
    }
    if (Val & (1 << P))
    {
        if (Node->Son[0]) return Query(Node->Son[0],P-1);
                          return (1 << P) + Query(Node->Son[1],P-1);
    }
    if (Node->Son[1]) return (1 << P) + Query(Node->Son[1],P-1);
                      return Query(Node->Son[0],P-1);
}

int main()
{
    freopen("xormax.in","r",stdin);
    freopen("xormax.out","w",stdout);

     scanf("%d",&N);

     i = 0;
     Add(T,21);

      for (i = 1;i <= N;i++)
      {
          scanf("%d",&Val);
          X[i] = X[i-1] ^ Val;
          Val = X[i];
          Value = X[i] ^ Query(T,21);

           if (Value > Sol)
           {
               Sol = Value;
               L = Ans + 1;
               R = i;
           }
           Add(T,21);
      }
      printf("%d %d %d",Sol,L,R);
}