Cod sursa(job #1450659)

Utilizator retrogradLucian Bicsi retrograd Data 14 iunie 2015 10:30:09
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>

using namespace std;
typedef int var;

bool Trie[1 << 22];
var Map[1 << 21];

void add(var val) {
    var node = 1;
    for(var i=20; i>=0; i--) {
        bool bit = (val >> i) & 1;
        Trie[node << 1 | bit] = 1;
        node = node << 1 | bit;
    }
}

var xormax(var val) {
    var node = 1;
    var rez = 0;
    for(var i=20; i>=0; i--) {
        bool bit = (val >> i) & 1;
        if(Trie[node << 1 | (bit ^ 1)])
            node = node << 1 | (bit ^ 1),
            rez += (1 << i);
        else
            node = node << 1 | bit;
    }
    return rez;
}


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

int main() {
    var n;
    fin>>n;

    var sum = 0, val;

    var maxxor = -1, b = -1, e = -1;

    for(var i=1; i<=n; i++) {
        Map[sum] = i;
        add(sum);

        fin>>val;
        sum ^= val;

        var pret = xormax(sum);
        if(pret > maxxor) {
            maxxor = pret;
            e = i;
            b = Map[sum ^ maxxor];
        }
    }

    fout<<maxxor<<" "<<b<<" "<<e;
    return 0;
}