Cod sursa(job #2536690)

Utilizator ApostolIlieDanielApostol Daniel ApostolIlieDaniel Data 2 februarie 2020 15:16:40
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <bits/stdc++.h>

using namespace std;


struct Trie {
    int nr, lst;
    Trie *fiu[2];
    Trie () {
        nr = lst = 0;
        fiu[0] = fiu[1] = 0;
    }
};


int now;

Trie *T = new Trie;

void upd (Trie *nod, int nr, int bit) {
    nod->lst = now;
    if (bit < 0) {
        return;
    }
    bool b = (1 << bit) & nr;
    if (nod->fiu[b] == NULL) {
        nod->fiu[b] = new Trie;
    }
    upd (nod->fiu[b], nr, bit - 1);
}


pair <int, int> best;

void go (Trie *nod, int nr, int bit, int val) {
    if (bit < 0) {
        best = {val, nod->lst};
        return;
    }
    bool b = (1 << bit) & nr;
    if (nod->fiu[1 - b] != NULL)
        go (nod->fiu[1 - b], nr, bit - 1, val + (1 << bit));
    else
        go (nod->fiu[b], nr, bit - 1, val);
}

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

    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);

    int n;
    cin >> n;
    int xr = 0;
    int x;
    int ans = -1, ansl = 0, ansr = 0;
    now = 0;
    upd (T, 0, 21);
    for (int i = 1; i <= n; i++) {
        cin >> x;
        now = i;
        xr ^= x;
        go (T, xr, 21, 0);
        if (best.first > ans) {
            ans = best.first;
            ansl = best.second + 1;
            ansr = i;
        }
        upd (T, xr, 21);
    }
    cout << ans << " " << ansl << " " << ansr << "\n";
    return 0;
}