Cod sursa(job #1449600)

Utilizator retrogradLucian Bicsi retrograd Data 10 iunie 2015 01:54:51
Problema Xor Max Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include<iostream>
#include<cstring>
#include<cstdio>
#include<unordered_map>
#include<vector>
#include<algorithm>

using namespace std;
typedef int var;

const var MAXBIT = 20;

struct Node {
    Node *leg[2];
    Node() { leg[0] = leg[1] = NULL; }
};
typedef Node* pnod;
pnod root = new Node();

vector<var> Ap[100001];
var Sum[100001];

unordered_map<var, var> Ind;

void insTree(var n, var ind) {
    pnod p = root;
    for(var i=MAXBIT; i>=0; i--) {
        bool b = (n >> i) & 1;

        if(p->leg[b] == NULL) {
            p->leg[b] = new Node();
        }

        p = p->leg[b];
    }
}

var xormax, start, stop = 200000;
var ind = 0;

void updateEnd(var a, var b) {

    vector<var> &V = Ap[Ind[b]];
    auto it = upper_bound(V.begin(), V.end(), Ap[Ind[a]][0]);
    if(it == V.end()) return;

    stop = min(stop, *it);
}

void getMax(pnod a, pnod b, var ai, var bi) {

    if(!a->leg[0] && !a->leg[1]) {
        if( xormax < (ai ^ bi) ) {
            xormax = ai ^ bi;
        }
        if( xormax == (ai ^ bi) ) {
            updateEnd(ai, bi);
            updateEnd(bi, ai);
        }
        return;
    }

    bool good = false;

    if(a->leg[0] && b->leg[1]) {
        getMax(a->leg[0], b->leg[1], ai<<1, bi<<1|1);
        good = true;
    }

    if(a->leg[1] && b->leg[0]) {
        getMax(a->leg[1], b->leg[0], ai<<1|1, bi<<1);
        good = true;
    }

    if(good) return;

    if(a->leg[0] && b->leg[0]) {
        getMax(a->leg[0], b->leg[0], ai<<1, bi<<1);
    }

    if(a->leg[1] && b->leg[1]) {
        getMax(a->leg[1], b->leg[1], ai<<1|1, bi<<1|1);
    }

}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    var n, sum = 0;
    cin>>n;

    insTree(0, 0);
    Ind[0] = 0;
    Ap[0].push_back(0);

    for(var i=1; i<=n; i++) {
        cin>>Sum[i];
        Sum[i] ^= Sum[i-1];

        if(Ind.find(Sum[i]) == Ind.end()) {
            Ind[Sum[i]] = ++ind;
        }

        Ap[Ind[Sum[i]]].push_back(i);
        insTree(Sum[i], i);
    }

    getMax(root, root, 0, 0);

    for(var i=stop-1; ;i--) {
        if(Sum[i] == (xormax ^ Sum[stop])) {
            cout<<xormax<<" "<<i+1<<" "<<stop;
            return 0;
        }
    }

    return 0;
}