Cod sursa(job #2289429)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 24 noiembrie 2018 16:32:15
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>

using namespace std;

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

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

trie *t = new trie();

const int nMax = 100000;
int n, xori[nMax + 5], solx, soly, maxim = -1;

void Add(trie *nod, int poz) {
    trie *fiu = nod;
    for (int i = 22; i >= 0; i--) {
        int k = ((xori[poz] & (1 << i)) > 0);
        if (fiu -> son[k] == 0)
            fiu -> son[k] = new trie();
        fiu = fiu -> son[k];
    }
    fiu -> poz = poz;
}

int Find(trie *nod, int nr) {
    trie *fiu = nod;
    for (int i = 22; i >= 0; i--) {
        int k = ((nr & (1 << i)) > 0) ;
        if (fiu -> son[k ^ 1] == 0)
            fiu = fiu -> son[k];
        else
            fiu = fiu -> son[k ^ 1];
    }
    return fiu -> poz;
}

int main() {
    fin >> n;

    Add(t, 0);
    for (int i = 1; i <= n; i++) {
        int nr;
        fin >> nr;
        xori[i] = xori[i-1] ^ nr;
        int poz = Find(t, xori[i]);
        if ((xori[i] ^ xori[poz]) > maxim) {
            maxim = xori[i] ^ xori[poz];
            solx = poz;
            soly = i;
        }
        Add(t, i);
    }
    fout << maxim << " " << solx + 1 << " " << soly << '\n';
}