Cod sursa(job #598538)

Utilizator cosmyoPaunel Cosmin cosmyo Data 26 iunie 2011 12:47:05
Problema Xor Max Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <cstdio>
#include <vector>
using namespace std;
const int N = 100005;
vector< vector < pair <int , char> > > t;
vector<int> trie;
vector<char> number;
int n, p[21];

inline int get_edge(int root, char c) {
    int i;
    for(i = 0 ;i < t[root].size(); ++i)
        if(t[root][i].second == c)
            return t[root][i].first;
    return -1;
}

inline void add(vector<char> number, int ind) {
    int next;
    int i, root = 0;
    for(i = 0; i < number.size(); ++i) {
        next = get_edge(root, number[i]);
        if(next == -1) {
            next = trie.size();
            trie.push_back(0);
            t.resize(trie.size());
            t[root].push_back(make_pair(next, number[i]));
        }

        root = next;
    }

    trie[root] = ind;
}

inline pair<int, int> find(vector<char> number) {
    int i, root = 0, next, j, sw, suma = 0;
    for(i = 0; i < number.size(); ++i){
        sw = 0;
        for(j = 0; j < t[root].size(); ++j)
            if(t[root][j].second != number[i]){
                next = t[root][j].first;
                sw = 1;
                suma += p[20 - i];
            }

        if(sw == 0)
            for(j = 0; j < t[root].size(); ++j)
                if(t[root][j].second == number[i])
                    next = t[root][j].first;
        root = next;
    }

    return make_pair(trie[root] + 1, suma);
}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);
    int i, a, max = 0, start = 1, stop = 2, s = 0;
    scanf("%d", &n);
    p[0] = 1;
    for(i = 1; i <= 22; ++i)
        p[i] = p[i - 1] * 2;

    trie.reserve(p[21] + 3);    trie.resize(1);
    t.reserve(p[21] + 3);   t.resize(1);
    for(int j = 1; j <= n; ++j) {
        scanf("%d ", &a);
        s ^= a;
        number.clear();
        for(i = 20; i >= 0; --i){
            int sw = p[i] & s;
            number.push_back(sw > 0 ? 1 : 0);
        }
     //   for(i = 0; i < number.size(); ++i)
     //       printf("%d", number[i]);
     //       printf("\n");
        pair<int, int> rez;

        if(j > 1){
            rez = find(number);
            if(max < rez.second) {
                max = rez.second;
                start = rez.first;
                stop = j;
            }
          //  printf("%d %d\n", rez.first, rez.second);
        }
        add(number, j);
    }

    printf("%d %d %d\n", max, start, stop);

    return 0;
}