Cod sursa(job #2364805)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 4 martie 2019 10:54:33
Problema Xor Max Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <fstream>
#include <cstring>

using namespace std;

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

const int NR_BITS = 21;
const int N_MAX = 100001;

int N;
int secv[N_MAX];

struct Trie {
    Trie *fiu[2]; //putem aveam maxim 2 fii (pentru bitii 0 si 1)
//constructor
    Trie() {
        memset(fiu, 0, sizeof(fiu));
    }
};
Trie *T = new Trie;

void insert(Trie *nod, int n, int b) {
    if(b == 0)
        return;
    int bit = (n & b) ? 1 : 0;
    if(nod->fiu[bit] == 0) //daca nu exista fiu, alocam memorie
        nod->fiu[bit] = new Trie;
    insert(nod->fiu[bit], n, b >> 1); //trecem la nivelul urmator, cu bitul urmator
}

int search(Trie * nod, int n, int res, int b) {
    if(nod->fiu[0] == 0 && nod->fiu[1] == 0) //daca nu exista fii
        return res;

    int bit = (n & b) ? 1 : 0;
    if(nod->fiu[bit ^ 1])   //daca exista numar cu bitul opus lui q
        return search(nod->fiu[bit ^ 1], n, res + b, b >> 1);

    if(nod->fiu[bit])  //daca nu exista numar cu bit opus, dar exista cu acelasi bit ca si q
        return search(nod->fiu[bit], n, res, b >> 1);
}

int nr_bits(int x) {
    int nr = 0;
    while((1 << nr) <= x)
        nr++;
    return nr;
}

int main() {
    int x, nrbits = 0, xormax = -1, start, finish, ans;
    in >> N;
    secv[0] = 0;
    for(int i = 1; i <= N; ++i) {
        in >> x;
        secv[i] = secv[i - 1] ^ x;
        nrbits = max(nrbits, nr_bits(secv[i]));
    }

    insert(T, 0, 1 << (nrbits - 1));
    for(int i = 1; i <= N; ++i) {
        ans = search(T, secv[i], 0, 1 << (nrbits - 1));
        if(ans > xormax) {
            xormax = ans;
            finish = i;
        }
        insert(T, secv[i], 1 << (nrbits - 1));
    }

    for(int i = 0; i < finish; ++i)
        if((secv[i] ^ secv[finish]) == xormax)
            start = i + 1;

    out << xormax << ' ' << start << ' ' << finish;

    return 0;
}