BFS optimized with SortedList
Intuition\nBFS, optimized to make sure that each unbanned position is only checked once.\n\n# Approach\n1. Convert banned to set and add p to it: We don\'t need
# Intuition\nBFS, optimized to make sure that each unbanned position is only checked once.\n\n# Approach\n1. Convert `banned` to `set` and add `p` to it: We don\'t need to visit the starting position again.\n2. Keep even & odd unbanned position separately in `SortedList`\n3. BFS, but the tricky part is figuring out the rules of flipping subarrays. From position `i`, the relevant and admittable starting position of the subarray goes from `max(0, i - k + 1)` (leftmost) to `min(n - k, i)` (rightmost). Whether the flipped position falls to the left or right of `i` depends on whether the center of the subarray `(starting position) + (k - 1) / 2` falls to the left or right of `i`. Calculate the range of possible flipped positions accordingly.\n4. Finally, parity also matters: if `k` is even, the flipped positions must have the opposite parity. if `k` is odd, the flipped positions must have the same parity. Traverse through the correct `SortedList` and add all the unbanned positions in the range to the next step.\n5. Repeat till no new positions can be reached per standard BFS.\n\n# Complexity\n- Time complexity:\n$$O(n \\log n)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:\n        banned = set(banned)\n        banned.add(p)\n        odd = k % 2\n        odd_sl = SortedList(i for i in range(1, n, 2) if i not in banned)\n        even_sl = SortedList(i for i in range(0, n, 2) if i not in banned)\n        ans = [-1] * n\n        ans[p] = 0\n        curr = [p]\n        step = 1\n        while curr:\n            new = []\n            for i in curr:\n                \n                leftmost = max(0, i - k + 1)\n                center2 = 2 * leftmost + k - 1\n                leftmost = center2 - i\n                \n                rightmost = min(n - k, i)\n                center2 = 2 * rightmost + k - 1\n                rightmost = center2 - i\n                \n                odd_i = i % 2\n                if odd:\n                    target = odd_sl if odd_i else even_sl\n                else:\n                    target = even_sl if odd_i else odd_sl\n                index = target.bisect_left(leftmost)\n                while index < len(target) and target[index] <= rightmost:\n                    next_i = target.pop(index)\n                    ans[next_i] = step\n                    new.append(next_i)\n            curr = new\n            step += 1\n        return ans\n```
['Python3']