Cod sursa(job #1652086)

Utilizator FullP0werMihalache Andrei FullP0wer Data 14 martie 2016 17:01:29
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cstdio>
#include <cstring>
#include <bitset>
#define Tmax 100001
#define n_bit 22
#define x b[index]
using namespace std;
long a[Tmax], N, s[Tmax], max_t, left = 1, right = 1;
bitset<n_bit> b;
struct Trie{
    int el, ord;
    Trie* next[2];
    Trie(){
        el = ord = 0;
        memset(next, 0, sizeof(next));
    }
};
Trie* T = new Trie;
void Insert(Trie* nod, int index, int ord){
    if (index < 0){
            nod->ord = ord;
            return;
    }
    if(!nod->next[x]){
        nod->next[x] = new Trie;
    }
    Insert(nod->next[x], index-1, ord);
}
long Find(long S){
    bitset<n_bit> n_bin(S);
    Trie* nod = T;
    for(int i = n_bit; i > -1; i--){
        if (nod->next[!n_bin[i]]){
            nod = nod->next[!n_bin[i]];
        }
        else{
            if (nod->next[n_bin[i]]){
                nod = nod->next[n_bin[i]];
            }
            else return -1;

        }
    }
    return nod->ord;
}
int main(){
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%ld", &N);
    for(int i = 1; i <= N; i++){
        scanf("%ld", a+i);
        s[i] = s[i-1] ^ a[i];
    }
    for(int i = 1; i <= N; i++){
        long f = Find(s[i]);
        if ((s[i] ^ s[f]) > max_t){
                left = f+1;
                right = i;
                max_t = s[i] ^ s[f];
        }
        b = bitset<n_bit>(s[i]);
        Insert(T, n_bit, i);
    }
    printf("%ld %ld %ld", max_t, left, right);
    return 0;
}