Cod sursa(job #2767477)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 6 august 2021 12:36:23
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

struct Trie {
    int start, nrfii;
    Trie *bin[2];

    Trie() {
        start = nrfii = 0;
        bin[0] = bin[1] = 0;
    }
};

Trie *T = new Trie;

int bit[21];
int istart;

void insert(Trie *nod, int Nrit, int idx) {
    if(idx == -1) {
        nod -> start = Nrit;
        return;
    }

    if(nod -> bin[bit[idx]] == 0) {
        nod -> bin[bit[idx]] = new Trie;
        nod -> nrfii++;
    }

    insert(nod -> bin[bit[idx]], Nrit, idx - 1);
}

int Search(Trie *nod, int idx) {
    if(idx == -1) {
        istart = nod -> start;
        return 0;
    }

    int inv = 1 - bit[idx];
    if(nod -> bin[inv] != 0)
        return (1 << idx) + Search(nod -> bin[inv], idx - 1);
    return Search(nod -> bin[bit[idx]], idx - 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //Open("");

    int N, mx = 0, sxor = 0, l = 1, r = 1;

    cin >> N;
    for(int i = 1, x;i <= N;i++) {
        cin >> x;
        if(i == 1) mx = x;
        sxor ^= x;

        for(int p = 0;p <= 20;p++)
            if(sxor & (1 << p)) bit[p] = 1;
            else bit[p] = 0;

        if(i > 1) {
            int val = Search(T, 20);
            if(val > mx) {
                mx = val;
                l = istart + 1, r = i;
            }
        }

        insert(T, i, 20);
    }

    cout << mx << " " << l << " " << r;
    
    return 0;
}