Cod sursa(job #1002064)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 26 septembrie 2013 20:18:26
Problema Xor Max Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<stdio.h>

#define NMAX 3
#define MMAX 100007

struct Trie{
    int Finish;
    Trie *sons[NMAX];
    Trie(){
        Finish = 0;
        sons[0] = sons[1] = 0;
    }
};

Trie *t = new Trie;
int n, Sum[MMAX], Ans = -1, Sol = -1, Pozi, Pozj, a;

int Search(Trie *Nod, int Number){
    bool Bit;
    for(int i = 22; i >= 0; -- i){
        Bit = (Number & (1 << i));
        if(Nod->sons[!Bit] != 0)
            Nod = Nod->sons[!Bit];
        else
            Nod = Nod->sons[ Bit];
    }
    return Nod->Finish;
}

void Add(Trie *Nod, int Number, int fin){
    bool Bit;
    for(int i = 22; i >= 0; -- i){
        Bit = (Number & (1 << i));
        if(Nod->sons[Bit] == 0)
            Nod->sons[Bit] = new Trie;
        Nod = Nod->sons[Bit];
    }
    Nod->Finish = fin;
}

int main(){
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%d", &n);
    Add(t, 0, 0);
    for(int i = 1; i <= n; ++ i){
        scanf("%d", &a);
        Sum[i] = Sum[i - 1] ^ a;
        Sol = Search(t, Sum[i]);
        if(Ans < Sum[i] ^ Sum[Sol]){
            Ans = Sum[i] ^ Sum[Sol];
            Pozi = Sol + 1;
            Pozj = i;
        }
        Add(t, Sum[i], i);
    }
    printf("%d %d %d\n", Ans, Pozi, Pozj);
    return 0;
}