Cod sursa(job #598785)

Utilizator cosmyoPaunel Cosmin cosmyo Data 27 iunie 2011 02:46:33
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <cstdio>
#include <utility>
using namespace std;
const int N = (1 << 21) + 3;
int t[N][2], n, trie[N], p[25], dim;

inline int get_edge(int root, int c) {
    int i;
    return t[root][c] > 0 ? t[root][c] : -1;
}

inline void add(int a, int ind) {
    int i, sw, root = 0, next ;
   // printf("%d\n", a);
    for(i = 20; i >= 0; --i) {
        sw = (a & p[i]) > 0;
    //    printf("%d", sw);
        next = get_edge(root, sw);
        if(next == -1) {
            ++dim;
            t[root][sw] = dim;
            next = dim;
        }
        root = next;
    }
  //  printf("\n");
    trie[root] = ind;
}

inline pair<int, int> find(int a) {
    int ok, i, root = 0, suma = 0, sw;
    for(i = 20; i >= 0; --i) {
        sw = (a & p[i]) > 0;
        ok = 0;
        if(t[root][!sw]){
            suma += p[i];
            root = t[root][!sw];
            ok = 1;
        }

        if(!ok)
            root = t[root][sw];
    }
    return make_pair(trie[root], suma);
}


int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    int i, j, a, start = 1, stop = 1, max = 0, s = 0;
    scanf("%d", &n);
    p[0] = 1;
    for(i = 1; i <= 23; ++i)
        p[i] = p[i - 1] * 2;
    for(i = 1; i <= n; ++i) {
        scanf("%d", &a);
        s ^= a;
        pair<int, int> rez;
        if(i > 1){
            rez = find(s);
            if(rez.second > max){
                max = rez.second;
                start = rez.first + 1;
                stop = i;
            }
        }
        else
            max = a;
        add(s, i);
    }
//    for(i = 0; i <= dim; ++i)
   //     printf("%d %d %d\n", t[i][0], t[i][1], trie[i]);
    printf("%d %d %d\n", max, start, stop);

    return 0;
}