3991. Sort Array Using Prefix Reversals

You are given an integer array nums of length n, where nums is a permutation of the integers in the range [0, n - 1].

You are also given an integer array pre, where each pre[i] is a valid prefix length.

In one operation, you may choose any length x from pre and reverse the first x elements of nums.

For example, applying a prefix reversal of length 3 on [4, 1, 2, 3] results in [2, 1, 4, 3].

Return the minimum number of operations required to sort nums in ascending order. If it is impossible to sort nums, return -1.

class Solution {
public:
    int sortArray(vector<int>& nums, vector<int>& pre) {
        set<vector<int>> vis;
        queue<vector<int>> q;
        vector<int> ok(nums.size());
        iota(begin(ok), end(ok),0);
        auto push = [&](vector<int> A) {
            if(vis.count(A)) return;
            vis.insert(A);
            q.push(A);
        };
        int res = 0;
        auto apply = [&](vector<int> A, int p) {
            for(int i = 0, j = p - 1; i < j; i++,j--) swap(A[i],A[j]);
            return A;
        };
        push(nums);
        while(q.size()) {
            int sz = q.size();
            while(sz--) {
                auto vec = q.front(); q.pop();
                if(vec == ok) return res;
                for(auto& p : pre) {
                    push(apply(vec,p));
                }
            }
            res++;
        }
        return -1;
    }
};