Cod sursa(job #1110601)

Utilizator Theorytheo .c Theory Data 18 februarie 2014 11:27:02
Problema Xor Max Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("xormax.in");
ofstream fout ("xormax.out");

const int NMAX = 100009;
const int MAXBIT = 22;

int N; int V[NMAX]; int res; int best_mask; int best_dr; int best;

class Trie {
    public:

    Trie *son[2];
    Trie() {
        memset(son, 0, sizeof(son));
    }
};

Trie* T = new Trie;

void init(Trie *X, int pos) {

    if(pos == -1) return;

    X -> son[0] = new Trie;
    init(X -> son[0], pos - 1);
}

void add(Trie *X, const int &value, int pos) {

    if(pos == -1) {
        return ;
    }
    int bit = (((1 << pos) & value) == (1 << pos));

    if(X -> son[bit] == 0) {

        X -> son[bit] = new Trie;
    }

    add(X -> son[bit], value, pos - 1);
}

void search(Trie* X, const int& value, int pos) {

    if(pos == -1) return;

    int bit = (value & (1 << pos) == (1 << pos));
    if(X -> son[bit]){
        res = (res << 1) + bit;
        search(X -> son[bit], value, pos - 1);
        return;
    }

    if(X -> son[(bit + 1) % 2]) {

        res = (res << 1) + ( (bit + 1) % 2 );
        search(X -> son[(bit + 1) % 2], value, pos - 1);
        return;
    }
    return;
}

int main() {

    int mask = 0;

    fin >> N;
    init(T, MAXBIT);
    for(int i = 1; i <= N; ++i) {

        int value;
        fin >> value; V[i] = value;

        mask ^= value; res = 0;

        int tofind = mask ^ ( (1 << MAXBIT) - 1);

        search(T, tofind, MAXBIT);

        add(T, mask, MAXBIT);

        int v = res ^ mask;

        if(v > best) {

            best_mask = res;
            best_dr = i;
            best = v;
        }
    }

    mask = 0;
    for(int i = 1; i <= best_dr; ++i) {
        mask ^= V[i];
        if(mask == best_mask) {
            fout << best << " " << i + 1 <<" " << best_dr <<'\n';
            break;
        }
    }

    return 0;
}