Cod sursa(job #1449589)

Utilizator retrogradLucian Bicsi retrograd Data 10 iunie 2015 00:46:27
Problema Xor Max Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include<iostream>
#include<cstring>
#include<cstdio>
#include<unordered_map>

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();

unordered_map<pnod, var> Map;
var Sum[100001];

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];
    }

    Map[p] = ind;
}

var xormax, start, stop;

void getMax(pnod a, pnod b) {

    if(!a->leg[0] && !a->leg[1]) {
        var i1 = Map[a], i2 = Map[b];
        var xorr = Sum[i1] ^ Sum[i2];
        if(xormax < xorr) {
            xormax = xorr;
            start = min(i1, i2) + 1;
            stop = max(i1, i2);
        }
        return;
    }

    bool good = false;

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

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

    if(good) return;

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

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

}

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

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

    insTree(0, 0);

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

        insTree(Sum[i], i);
    }

    getMax(root, root);
    cout<<xormax<<" "<<start<<" "<<stop;
    return 0;
}