Cod sursa(job #1449592)

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

using namespace std;
typedef int var;

const var MAXBIT = 20;

const var ADD = (1 << 21);
bool Gets[ADD << 1];

unordered_map<var, var> Map;

var Sum[100001];

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

        Gets[node*2+b] = 1;
        node = node*2 + b;
    }
}

var xormax, start, stop;

void getMax(var a, var b) {

    if(a >= ADD) {
        var rez = (a-ADD) ^ (b-ADD);

        if(xormax < rez) {
            xormax = rez;

            var i1 = Map[a-ADD],
                i2 = Map[b-ADD];

            start = min(i1, i2) + 1;
            stop = max(i1, i2);
        }

        return;
    }

    bool good = false;

    if(Gets[2*a] && Gets[2*b+1])
        getMax(2*a, 2*b+1), good=true;

    if(Gets[2*a+1] && Gets[2*b])
        getMax(2*a+1, 2*b), good=true;

    if(good) return;

    if(Gets[2*a] && Gets[2*b])
        getMax(2*a, 2*b);

    if(Gets[2*a+1] && Gets[2*b+1])
        getMax(2*a+1, 2*b+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];
        Map[Sum[i]] = i;

        insTree(Sum[i], i);
    }

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