Cod sursa(job #2814056)

Utilizator ElizaTElla Rose ElizaT Data 7 decembrie 2021 15:20:33
Problema Xor Max Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;

const int NRFII = 2,NMAX = 1e5,BITS = 20;
struct trie {
    int poz;
    trie *fii[NRFII];
    trie() {
        poz = 0;
        for (int i = 0;i < NRFII;i++)
            fii[i] = nullptr;
    }
};
trie* t = new trie();
int s[NMAX + 5];

void update (trie* node, int val, int poz, int bit) {
    if (bit == 0) {
        node -> poz = poz;
        return;
    }
    bool msb = (val & (1 << bit));
    if (node -> fii[msb] == nullptr)
        node -> fii[msb] = new trie();
    update(node -> fii[msb], val, poz, bit - 1);
}
int query (trie* node, int val, int bit) {
    if (bit == 0)
        return node -> poz;
    bool msb = (val & (1 << bit));
    msb ^= 1;
    if (node -> fii[msb] != nullptr)
        return query(node -> fii[msb], val, bit - 1);
    return query(node -> fii[(msb ^ 1)], val, bit - 1);
}
int main()
{
    ifstream fin("xormax.in");
    ofstream fout("xormax.out");
    int n,x,a,pozi = 0,pozj = 0,mx = -1;
    fin >> n;
    update(t, 0, 0, BITS);
    for (int i = 1;i <= n;i++) {
        fin >> x;
        s[i] = (s[i - 1] ^ x);
        a = query(t, s[i], BITS);
        if ((s[a] ^ s[i]) > mx) {
            mx = (s[a] ^ s[i]);
            pozi = a;
            pozj = i;
        }
        update(t, s[i], i, BITS);
    }
    fout << mx << " " << pozi + 1 << " " << pozj;
    return 0;
}