Cod sursa(job #2019091)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 6 septembrie 2017 22:15:47
Problema Xor Max Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <cassert>

using namespace std;

struct Trie {
    int term;
    Trie* fii[2];
};

Trie* root = new Trie();

void add(Trie* nod, int n, int pos, int b = 20) {
    if(b == -1) {
        nod->term = pos;
    } else {
        int am = ((n & (1 << b)) > 0);
        if(nod->fii[am] == NULL) {
            nod->fii[am] = new Trie();
        }
        add(nod->fii[am], n, pos, b - 1);
    }
}

int solve(Trie* nod, int n, int &pos, int b = 20, int rasp = 0) {
    if(b == -1) {
        pos = nod->term;
        return rasp;
    } else {
        int am = ((n & (1 << b)) > 0), adun = (1 << b);
        if(nod->fii[1 - am] == NULL) {
            am = 1 - am;
            adun = 0;
        }
        return solve(nod->fii[1 - am], n, pos, b - 1, rasp + adun);
    }
}

int main() {
    freopen("xormax.in", "r", stdin);
    freopen("xormax.out", "w", stdout);

    int n, rasp, sp, st, dr;
    scanf("%d", &n);

    for(int i = 1; i <= n; ++ i) {
        int x, pos = 0;
        scanf("%d", &x);

        if(i > 1) {
            sp = sp ^ x;
            int posibil = solve(root, sp, pos);
            if(posibil > rasp) {
                rasp = posibil;
                st = pos;
                dr = i;
            }
        } else {
            rasp = x;
            sp = x;
            st = 0;
            dr = 1;
        }

        add(root, sp, i);
    }

    printf("%d %d %d\n", rasp, st + 1, dr);

    return 0;
}