Cod sursa(job #1004659)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 octombrie 2013 14:08:34
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
using namespace std;

const int MAX_N = 100002;

struct Trie {
    Trie() {
        next[0] = next[1] = NULL;
    }

    int pos;
    Trie *next[2];
};

int N, sol = -1, Beg, End;
int S[MAX_N];
Trie *root = new Trie;

inline int search(int val) {
    Trie *node = root;
    for(int i = 20; i >= 0; --i) {
        int bit = ((1 << i)&val);
        if(bit)
            bit = 1;
        if(node->next[!bit])
            node = node->next[!bit];
        else node = node->next[bit];
    }

    return node->pos;
}

inline void insert(int val, int p) {
    Trie *node = root;
    for(int i = 20; i >= 0; --i) {
        int bit = ((1 << i)&val);
        if(bit)
            bit = 1;
        if(node->next[bit] == NULL)
            node->next[bit] = new Trie;
        node = node->next[bit];
    }
    node->pos = p;
}

int main() {
    ifstream f("xormax.in");
    ofstream g("xormax.out");

    insert(0, 0);

    f >> N;
    for(int i = 1, x; i <= N; ++i) {
        f >> x;
        S[i] = x^S[i-1];
        int ind = search(S[i]);
        if((S[ind] ^ S[i]) > sol)
            sol = S[ind] ^ S[i], Beg = ind + 1, End = i;
        insert(S[i], i);
    }

    g << sol << " " << Beg << " " << End << "\n";

    f.close();
    g.close();

    return 0;
}