C++, using BFS and set, O(nlogn) 100% 100% for the moment
Intuition\n After every operation, there is always only one \'1\' in the <code>arr</code>, hence we only need to remember this number and current number of oper
# Intuition\n<!-- After every operation, there is always only one \'1\' in the ```arr```, hence we only need to remember this number and current number of operations. -->\nFor each index ```i```, we need to find after how many operations ```arr[i]``` could be ```1```. Hence, we can do BFS by saving statuses```(idx, ops)``` where ```arr[idx] == 1``` is achievable after ```ops``` operations.\n\nIf ```arr[i] == 1```, how can we find all ```j``` such that ```arr[j] == 1``` is achievable after 1 operation? \n\nTo answer this question, first, suppose the size of subarray that we choose to reverse is ```k```. If this subarray is ```[a, a + k - 1]```, after 1 operations, the index ```a``` will be moved to index ```a + k - 1```, ```a + 1``` will be moved to ```a + k - 2``` etc. \nThis shows that for all the indices within this subarray: __current index + index after operation = constant__. \nSo, if we know that the reversed subarray is ```[a, a + k - 1]```, index ```i``` will be moved to ```2*a + k - 1  - i``` after operation.\n\nSecond, we need to know all the possible ```a``` ( starting index of the subarray ) for a given ```i``` where ```arr[i] == 1```. Note that ```i``` needs to be within ```[a, a + k - 1]```, otherwise the operation makes no difference on ```arr```. So, we can find that for the leftmost possible subarray, ```a == max(0, i - k + 1)```, and for the rightmost,```a == min(n - k, i)```. As for now, we have enough information to answer the question: \n```\nfor (int a = max(0, i - k + 1) ; a <= min(n - k, i) ; ++a) {\n    int j = 2 * a + k - 1 - i;\n    // ...\n}\n```\nand ```j``` is the possible index for ```arr[j]``` to be 1 after 1 operation. Note that the parity of ```j``` remains the same during the whole operations\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. We need  a ```queue<pair<int,int> > statuses``` to save the statuses ```(idx, ops)```, the initial status is ```(p, 0)```\n\n2. While doing BFS, the earlier we save a status, the ```ops``` must be smaller or same. Because we are looking for the smallest number of operations, there is no need to save a status where ```idx``` is already used before\n\n    To achieve this, we need to memorize all the indices that have been used. The intuition is to use a ```vector<bool> used``` to record it. However, there is a faster way.\n\n    As we can see, for a given current index ```i```, all the ```j``` that is the possible index after one operation __remains the same parity__. For instance, this loop\n    ```\n    for (int a = max(0, i - k + 1) ; a <= min(n - k, i) ; ++a) {\n        int j = 2 * a + k - 1 - i;\n        // ...\n    }\n    ```\n\n    is the same as this loop\n    ```\n    for (int j =  2 * max(0, i - k + 1) + k - 1 - i ; \n        j <= 2 * min(n - k, i) + k - 1 - i ; j += 2) {\n        // ...\n    }\n    ```\n    Hence, we can use two sets, save the __unvisited and unbanned__ indices for odds and evens respectively. And for every current index ```i```, we determine the parity of possible indices after 1 operation, then every index in the set that is within the range will be put in ```statuses``` for further iterations.\n\n    \n\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        // create a boolean array to check if index i is banned in linear time\n        vector<bool> isBanned(n, false);\n         for (auto &i : banned)\n            isBanned[i] = true;\n\n        // create return array, which will be the return value\n        vector<int> ret(n, -1);\n        // because arr[p] is 1 without any operation, ret[p] is assigned 0        \n        ret[p] = 0;\n\n        if (k == 1) // in this case, arr remains invariant after every operation\n            return ret;\n\n\n        // create two sets, for odd and even indices respectively\n        set<int> odd, even;\n        for (int i = 0 ; i < n ; ++i) {\n            if (!isBanned[i]) {\n                if (i % 2) {\n                    odd.insert(i);\n                }\n                else {\n                    even.insert(i);\n                }\n            }\n        }\n        \n        queue<pair<int,int> > statuses; // (idx, ops)\n\n        // initial status\n        statuses.push(make_pair(p, 0));\n        if (p % 2)\n            odd.erase(odd.find(p));\n        else\n            even.erase(even.find(p));\n\n        while (!statuses.empty()) {\n            auto tmp = statuses.front();\n            statuses.pop();\n            \n            int i = tmp.first, ops = tmp.second;\n            \n            // the smallest and biggest possible index after 1 operation\n            int smallest = 2 * max(0, i - k + 1) + k - 1 - i, biggest = 2 * min(n - k, i) + k - 1 - i;\n\n            // determine the parity of possible indices after 1 operation\n            if (smallest % 2) { // find in odd\n\n                for (auto it = odd.lower_bound(smallest) ; it != odd.end() && *it <= biggest ;) {\n                    statuses.push(make_pair(*it, ops + 1));\n                    ret[*it] = ops + 1;\n                    odd.erase(it++);\n                }\n\n            }\n            else { // find in even\n\n                for (auto it = even.lower_bound(smallest) ; it != even.end() && *it <= biggest ;) {\n                    statuses.push(make_pair(*it, ops + 1));\n                    ret[*it] = ops + 1;\n                    even.erase(it++);\n                }\n            }\n            \n        }\n        \n        return ret;\n    }\n};\n```
['C++']