Cod sursa(job #1004655)

Utilizator Mihai22eMihai Ionut Enache Mihai22e Data 3 octombrie 2013 14:03:41
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 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, 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;
        else if(S[ind] ^ S[i] == sol && i - ind < end - beg)
            beg = ind + 1, end = i;
        insert(S[i], i);
    }

    g << sol << " " << beg << " " << end << "\n";

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

    return 0;
}