Cod sursa(job #2407332)

Utilizator eduardcadarCadar Eduard eduardcadar Data 16 aprilie 2019 19:36:30
Problema Xor Max Scor 25
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("xormax.in");
ofstream g("xormax.out");
#define nmax 100001
int n, x, y, s[nmax], VAL2, sol, j, maxi;
struct trie{
    bool nr;
    int poz;
    trie *fiu[2];
    trie() {
        nr = false;
        fiu[0] = fiu[1] = 0;
    }
} *T;
void ins(trie *nod, int a, int val, int pozitie) {
    if (a==val) {nod->nr = true, nod->poz = pozitie; return;}
    if (nod->fiu[bool(a&(val>>1))] == 0) nod->fiu[bool(a&(val>>1))] = new trie;
    ins(nod->fiu[bool(a&(val>>1))], a - (bool(a&val) * val), val>>1, pozitie);
}
int cautare(trie *nod, int a, int val) {
    if (nod->nr) {j = nod->poz; return val;}
    if (nod->fiu[!(a&(val>>1))]) return cautare(nod->fiu[!(a&(val>>1))], a, val>>1);
    if (nod->fiu[1]) return -1;
    return cautare(nod->fiu[bool(a&(val>>1))], a, val>>1);
}
int main()
{
    T = new trie;
    f >> n;
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
        f >> x;
        s[i] = x^s[i - 1];
    }
    maxi = s[1], x = y = 1;
    VAL2 = 1;
    for (int i = 1; i <= 22; ++i) VAL2 = VAL2<<1;
    ins(T,0,VAL2,0), ins(T,s[1],VAL2,1);
    for (int i = 2; i <= n; ++i) {
        sol = cautare(T,s[i],VAL2);
        if (sol != -1) {
            sol = s[i]^sol;
            if (sol > maxi) maxi = sol, x = j + 1, y = i;
        }
        else {
            sol = s[i - 1]^s[i];
            if (sol > maxi) maxi = sol, x = y = i;
        }
        ins(T,s[i],VAL2,i);
    }
    g << maxi << ' ' << x << ' ' << y << '\n';
    return 0;
}