HackerRank Algebra – The Black Box – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Challenge: The Black Box

Subdomeniu: Algebra (algebra)

Scor cont: 150.0 / 150

Submission status: Accepted

Submission score: 1.0

Submission ID: 464812801

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/black-box-1/problem

Cerinta

Let's define a new data structure - black box. A black box is a data structure that is capable of performing the following operations:

- add an integer to the black box
- delete an integer from the black box
- find the subset from the set of numbers present inside the black box which produce a maximal value after being [XOR](https://en.wikipedia.org/wiki/Exclusive_or)ed.

We will give you *N* queries. Each query is an addition or a deletion operation as mentioned above. After each query we ask you to find the maximal possible [XOR](https://en.wikipedia.org/wiki/Exclusive_or) that can be obtained by combining some of the numbers that are present in the black box.

**Input Format**  
The first line of input contains an integer *N*.  
Then there is a line with *N* integers, separated with single spaces. Some of the integers are positive while some are negative.  

Let's denote the i<sup>th</sup> such integer by *A<sub>i</sub>*. If it's positive, then it corresponds to the addition operation: addition of *A<sub>i</sub>* to the black box. Otherwise, it corresponds to the deletion operation: deletion of |*A<sub>i</sub>*| from the black box.

It is guaranteed that:

- we will never add a number that is already present in the black box.
- we will never delete a number that is currently not present in the black box.

**Output Format**

After each query, output the maximal XOR in a new line. If the black box has no numbers after the query, output `0`. 

**Constraints**

1 ≤ *N* ≤ 5 * 10<sup>5</sup>  
0 < |*A<sub>i</sub>*| ≤ 2 * 10<sup>9</sup>  

**Sample Input**

<pre>6
1 2 3 4 -2 -3</pre>

**Sample Output**

<pre>1
3
3
7
7
5</pre>

**Explanation**

+ 1st Operation A = [1], maximum XOR is 1. 
+ 2nd Operation A = [1,2], maximum XOR is 1⊕2 = 3
+ 3rd Operation A = [1,2,3], maximum XOR is 1⊕2 or 3 = 3
+ 4th Operation A = [1,2,3,4], maximum XOR is 4⊕3 = 7
+ 5th Operation A = [1,3,4], maximum XOR is 4⊕3 = 7
+ 6th Operation A = [1,4], maximum XOR is 4⊕1 = 5

**TimeLimit**

The timelimits for this challenge is given [here](http://hr-testcases.s3.amazonaws.com/3133/tl.json), there might be chances of some submissions written in python TLEing post rerun on additional testcases, we will provide scores on a per submission basis if such a situation arises.

Cod sursa

#include <bits/stdc++.h>
using namespace std;

struct Basis {
    static const int MAXB = 30; // values <= 2e9
    int b[MAXB + 1];
    Basis() { memset(b, 0, sizeof(b)); }

    void add(int x) {
        for (int i = MAXB; i >= 0 && x; --i) {
            if (((x >> i) & 1) == 0) continue;
            if (!b[i]) {
                b[i] = x;
                return;
            }
            x ^= b[i];
        }
    }

    int getMax() const {
        int res = 0;
        for (int i = MAXB; i >= 0; --i) {
            res = max(res, res ^ b[i]);
        }
        return res;
    }
};

int N;
vector<vector<int>> seg;
vector<int> ans;

void addInterval(int node, int l, int r, int ql, int qr, int v) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
        seg[node].push_back(v);
        return;
    }
    int mid = (l + r) >> 1;
    addInterval(node << 1, l, mid, ql, qr, v);
    addInterval(node << 1 | 1, mid + 1, r, ql, qr, v);
}

void dfs(int node, int l, int r, Basis basis) {
    for (int v : seg[node]) basis.add(v);
    if (l == r) {
        ans[l] = basis.getMax();
        return;
    }
    int mid = (l + r) >> 1;
    dfs(node << 1, l, mid, basis);
    dfs(node << 1 | 1, mid + 1, r, basis);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;
    vector<int> A(N + 1);
    for (int i = 1; i <= N; ++i) cin >> A[i];

    seg.assign(4 * N + 5, {});
    ans.assign(N + 1, 0);

    unordered_map<int, int> st;
    st.reserve((size_t)N * 2);

    for (int i = 1; i <= N; ++i) {
        int x = A[i];
        if (x > 0) {
            st[x] = i;
        } else {
            int v = -x;
            auto it = st.find(v);
            int l = it->second;
            st.erase(it);
            if (l <= i - 1) addInterval(1, 1, N, l, i - 1, v);
        }
    }

    for (auto &kv : st) {
        int v = kv.first;
        int l = kv.second;
        if (l <= N) addInterval(1, 1, N, l, N, v);
    }

    Basis init;
    dfs(1, 1, N, init);

    for (int i = 1; i <= N; ++i) {
        cout << ans[i] << '\n';
    }
    return 0;
}

HackerRank Algebra – The Black Box