Cod sursa(job #1650649)

Utilizator FullP0werMihalache Andrei FullP0wer Data 11 martie 2016 19:39:04
Problema Xor Max Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <cstring>
#include <bitset>
#include <vector>
#include <iostream>
#define Tmax 100001
#define Nr_B 22
#define Nr_A 2
using namespace std;
long N, a[Tmax], s[Tmax], max_t = -1, begin_t = 1, end_t = 1;
bitset <Nr_B> b;
struct Trie{
    long nr, end;
    Trie* next[Nr_A];
    Trie(){
        nr = 0;
        end = Tmax;
        memset(next, 0, sizeof(next));
    }
};
void Insert(Trie* nod, int index, int end){
    if (index == -1){
        if (nod->end > end)
        nod->end = end;
        nod->nr++;
        return;
    }
    int temp = b[index];
    if(nod->next[b[index]] == 0){
            nod->next[b[index]] = new Trie;
    }
    Insert(nod->next[b[index]], index-1, end);
}
long Find(Trie* nod, int index){
    if(index == -1){
        return nod->end;
    }
    else{
        if(nod->next && nod->next[!b[index]] == 0){
            if(nod->next[0]) return Find(nod->next[0], index-1);
            else if(nod->next[1]) return Find(nod->next[1], index-1);
                 else return -1;
        }
        else{
            return Find(nod->next[!b[index]], index-1);
        }
    }
}
int main(){
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    scanf("%ld", &N);
    Trie* T = new Trie;
    for(int i = 1; i <= N; i++){
        scanf("%ld", &a[i]);
        s[i] = (a[i] ^ s[i-1]);
        b = bitset<Nr_B>(s[i]);
        long F = Find(T, Nr_B-1);
        long max_p = 0, begin_p = 1, end_p = 1;
        max_p = (s[i] ^ s[F]);
        begin_p = F != -1 ? F+1 : begin_p;
        end_p = i;
        if(max_p > max_t){
            max_t = max_p;
            begin_t = begin_p;
            end_t = end_p;
        }
        if(max_p == max_t){
                if(end_p - begin_p > 0 && end_p - begin_p < end_t - begin_t){
                        begin_t = begin_p;
                        end_t = end_p;
                }
        }
        Insert(T, Nr_B-1, i);
    }
     printf("%ld %ld %ld\n", max_t, begin_t, end_t);
    return 0;
}