Cod sursa(job #2407455)

Utilizator eduardcadarCadar Eduard eduardcadar Data 16 aprilie 2019 21:20:22
Problema Xor Max Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 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) return nod->poz;
    if (nod->fiu[!(a&(val>>1))]) return cautare(nod->fiu[!(a&(val>>1))], a, val>>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;
    VAL2 = VAL2<<22;
    ins(T,0,VAL2,0), ins(T,s[1],VAL2,1);
    for (int i = 2; i <= n; ++i) {
        sol = cautare(T,s[i],VAL2);
        j = sol;
        sol = s[i]^s[j];
        if (sol > maxi) maxi = sol, x = j + 1, y = i;
        ins(T,s[i],VAL2,i);
    }
    g << maxi << ' ' << x << ' ' << y << '\n';
    return 0;
}