Cod sursa(job #1810553)

Utilizator BlackLordFMI Alex Oprea BlackLord Data 20 noiembrie 2016 10:42:31
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include<fstream>
#include<cstring>
#define c *p

using namespace std;

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

struct Trie {
    int po;
    Trie *fiu[2];
    Trie() {
        po = 0;
        memset(fiu, 0, sizeof(fiu));
    }
};

int A, x, st, dr, poz, pot, val, j, S, a, t, n, best, i;
char s[30];

Trie *r=new Trie;

int cauta(Trie *nod, char *p) {
    if (c == 'a') {
        if(nod->po) {
            return 1;
        }
        return 0;
    }
    if (nod->fiu[c] != NULL) {
        return cauta(nod->fiu[c], p + 1);
    }
    return 0;
}

void baga(Trie *nod, char *p) {
    if (c == 'a') {
        nod->po = i;
        return;
    }
    if (nod->fiu[c] == NULL) {
        nod->fiu[c] = new Trie;
    }
    baga(nod->fiu[c], p + 1);
}

void rez(Trie *nod, char *p) {
    pot >>= 1;
    if (c == 'a') {
        poz = nod->po;
        return;
    }
    if (nod->fiu[!c] != NULL) {
        A |= pot * (!c);
        rez(nod->fiu[!c], p + 1);
    } else {
        A |= pot * c;
        rez(nod->fiu[c], p + 1);
    }
}
int main () {
    fin >> n;
    s[23] = 'a';
    i = 0;
    baga(r, s);
    best = -1;
    for (i = 1; i <= n; ++i) {
        fin >> x;
        S ^= x;
        a = S;
        t =- 1;
        while (a) {
            t++;
            if (a&1) {
                s[t] = 1;
            }
            a >>= 1;
        }
        for (j = 0; j <= 11; ++j) {
            swap(s[j], s[22 - j]);
        }
        A = 0;
        pot = (1 << 23);
        rez(r, s);
        val = A ^ S;
        if (val > best) {
            best = val;
            st = poz;
            dr = i;
        }
        baga(r, s);
        memset(s, 0, 23);
    }
    fout << best << " " << st + 1 << " " << dr;
    return 0;
}