Cod sursa(job #1014889)

Utilizator poptibiPop Tiberiu poptibi Data 23 octombrie 2013 17:17:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

const int NMAX = 100010, INF = 0x3f3f3f3f;

struct Trie 
{
    int Pos;
    Trie *Son[2];
    
    Trie()
    {
        memset(Son, 0, sizeof(Son));
        Pos = 0;
    }
};

Trie *T = new Trie();

int N, V[NMAX], Xor[NMAX], Ans = -INF, Left, Right, NowVal, NowPos;

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

void Find(Trie *Node, int P, int Val)
{
    if(P == 0)
    {
        NowPos = Node -> Pos;
        return ;
    }
    P --;
    int Bit = (Val & (1 << P)) > 0;
    if(Bit == 0)
    {
        if(Node -> Son[1]) NowVal += (1 << P), Find(Node -> Son[1], P, Val);
        else Find(Node -> Son[0], P, Val);
    }else 
    {
        if(Node -> Son[0]) Find(Node -> Son[0], P, Val);
        else NowVal += (1 << P), Find(Node -> Son[1], P, Val);
    }    
}

int main()
{
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    
    scanf("%i", &N);
    Insert(T, 21, 0, 0);

    for(int i = 1; i <= N; ++ i)
    {
        scanf("%i", &V[i]);
        Xor[i] = Xor[i - 1] ^ V[i];
        
        NowVal = NowPos = 0;
        Find(T, 21, Xor[i]);
        
        if((NowVal ^ Xor[i]) > Ans)
            Ans = (NowVal ^ Xor[i]), Left = NowPos, Right = i;
        
        Insert(T, 21, Xor[i], i);
    }
    
    printf("%i %i %i\n", Ans, Left + 1, Right);
    return 0;
}