2612. Minimum Reverse Operations

You are given an integer n and an integer p in the range [0, n - 1]. Representing a 0-indexed array arr of length n where all positions are set to 0‘s, except position p which is set to 1.

You are also given an integer array banned containing some positions from the array. For the i**th** position in banned, arr[banned[i]] = 0, and banned[i] != p.

You can perform multiple operations on arr. In an operation, you can choose a subarray with size k and reverse the subarray. However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.

Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.

• A subarray is a contiguous non-empty sequence of elements within an array.
• The values of ans[i] are independent for all i‘s.
• The reverse of an array is an array containing the values in reverse order.

class Solution {
public:
    vector<int> minReverseOperations(int n, int p, vector<int>& A, int k) {
        vector<int> res(n, INT_MAX);
        for(auto a : A) res[a] = -1;
        res[p] = 0;
        set<int> st1, st2;
        for(int i = 0; i < n; i++) if(res[i] == INT_MAX) {
            if(i & 1) st1.insert(i);
            else st2.insert(i);
        }
        queue<int> q;
        q.push(p);
        while(q.size()) {
            int u = q.front(); q.pop();
            int l = u - k + 1>= 0 ? u - k + 1: k - u - 1;
            int r = u + k - 1 < n ? u + k - 1 : n - k + (n - u - 1);
            if(l > r) swap(l,r);
            vector<int> erase;
            set<int>& st = (l & 1 ? st1 : st2);
            for(auto it = st.lower_bound(l); it != end(st) and *it <= r; it++) {
                erase.push_back(*it);
                res[*it] = res[u] + 1;
                q.push(*it);
            }
            for(auto e : erase) st.erase(e);
        }
        for(int i = 0; i < n; i++) if(res[i] == INT_MAX) res[i] = -1;
        return res;
    }
};