Cod sursa(job #1739707)

Utilizator mariusn01Marius Nicoli mariusn01 Data 9 august 2016 23:38:05
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
// consideram sumele xor partiale si scrierile lor pe acelasi numar de biti
// (numarul maxim de biti necesari pentru scrierea vreuneia).
// inseram intr-un trie scrierile in baza 2 ale acestor sume (incepand cu BITUL CEL MAI
// SEMNIFICATIV) dar, inainte sa inseram suma curenta interogam trie-ul (care contine sumele
// de pe pozitiile anterioare!) si cautam pe una care sa difere, in primul rand printr-un bit
// cat mai de sus si tot asa pentru urmatorii biti ...
#include <fstream>
#define DIM 100010

using namespace std;

int maxim, stmaxim, drmaxim, n, maxx, nr, pozsol, x;
int s[DIM];

struct trie {
    trie *f[2];
    int poz;
    trie () {
        f[0] = f[1] = 0;
        poz = 0;
    }
};

trie *r;

void inserare(trie *r, int bit, int val, int poz) {
    if (bit == -1) {
        r->poz = poz;
        return;
    }

    if (((val>>bit) & 1) == 0) {
        if (r->f[0] == NULL)
            r->f[0] = new trie();
        inserare(r->f[0], bit-1, val, poz);
    } else {
        if (r->f[1] == NULL)
            r->f[1] = new trie();
        inserare(r->f[1], bit-1, val, poz);
    }
}

void cauta(trie *r, int bit, int val) {
    if (bit == -1) {
        pozsol = r->poz;
        return;
    }

    int bitval = ((val >> bit) & 1);
    if (r->f[1-bitval] != 0) {
        cauta(r->f[1-bitval], bit-1, val);
    } else {
        cauta(r->f[bitval], bit-1, val);
    }

}

int main () {
    ifstream fin ("xormax.in");
    ofstream fout("xormax.out");
    fin>>n>>s[1];
    maxim = -1;
    for (int i=2;i<=n;i++) {
        fin>>x;
        if (x > maxx)
            maxx = x;
        s[i] = (x ^ s[i-1]);
    }

    while (maxx) {
        nr++;
        maxx/=2;
    }

    r = new trie();
    inserare(r, nr, 0, 0);
    for (int i=1;i<=n;i++) {

        cauta(r, nr, s[i]);
        if ((s[i] ^ s[pozsol]) > maxim) {
            maxim = (s[i] ^ s[pozsol]);
            stmaxim = pozsol+1;
            drmaxim = i;
        }
        inserare(r, nr, s[i], i);
    }
    fout<<maxim<<" "<<stmaxim<<" "<<drmaxim;
    return 0;
}