Cod sursa(job #2101259)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 7 ianuarie 2018 00:52:28
Problema Xor Max Scor 75
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
using namespace std;
ifstream in ("xormax.in");
ofstream out ("xormax.out");
int y,alfa,beta,num;
struct trie {
    trie *bit[2];
    int numar;
    trie() {
        bit[0] = NULL;
        bit[1] = NULL;
        numar = 0;
    }
};
int p[23],n,v[100001],maxim;
bool s[23];
trie *radacina = new trie;
void change (int x)  {
    int k = -1;
    for (int i = 0; i <= 21; i ++) {
        s[i] = 0;
    }
    while (x > 0) {
        s[++k] = x % 2;
        x /= 2;
    }
    for (int i = 0; i <= 11; i ++) {
        swap (s[i],s[21-i]);
    }
    return;
}
void adauga (trie *&nod, int i, int dr) {
    if (i == 22) {
        nod -> numar = dr;
        return;
    }
    if (nod -> bit[s[i]] == NULL) {
        nod -> bit[s[i]] = new trie;
    }
    adauga(nod -> bit[s[i]], i + 1,dr);
    return;
}
int cauta (trie *&nod, int i) {
    if (i == 22) {
        y = nod -> numar;
        return 0;
    }
    if (nod -> bit[1-s[i]] != NULL) {
        return p[(21-i)] + cauta(nod -> bit[1-s[i]],i+1);
    }
    else {
        return cauta(nod -> bit[s[i]],i+1);
    }
}
int main (void) {
    in >> n;
    for (int i = 1; i <= n; i ++) {
        in >> v[i];
    }
    for (int i = 1; i <= n; i ++) {
        v[i] = v[i] xor v[i-1];
    }
    p[0] = 1;
    for (int i = 1; i <= 22; i ++) {
        p[i] = p[i-1] * 2;
    }
    maxim = -1;
    change(0);
    adauga (radacina,0,0);
    for (int i = 1; i <= n; i ++) {
        change(v[i]);
        num = cauta(radacina,0);
        if (num > maxim) {
            maxim = num;
            alfa = i;
            beta = y;
        }
        adauga (radacina,0,i);
    }
    out << maxim << " " << beta + 1 <<" "<< alfa <<" ";
    return 0;
}