Cod sursa(job #1449594)

Utilizator retrogradLucian Bicsi retrograd Data 10 iunie 2015 01:22:01
Problema Xor Max Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.92 kb
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#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 = 200000;
var n;

vector< pair<var, var> >Sols;

void getMax(var a, var b) {

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

        if(xormax < rez) {
            xormax = rez;
            Sols.clear();
        }

        if(xormax == rez) {
            Sols.push_back(make_pair(a-ADD, b-ADD));
        }

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


}

void getLims(var a, var b) {
    var i;
    for(i=0; i<=n && Sum[i] != a; i++);

    var be = i;
    for(;i<=n && Sum[i] != b; i++) {
        if(Sum[i] == a)
            be = i;
    }
    var en = i;

    if(stop > en) {
        start = be;
        stop = en;
    }
}

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

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

    for(auto p: Sols) {
        getLims(p.first, p.second);
        getLims(p.second, p.first);
    }


    cout<<xormax<<" "<<start+1<<" "<<stop;
    return 0;
}