• + 0 comments
    /*
     * Complete the 'almostSorted' function below.
     *
     * The function accepts INTEGER_ARRAY arr as parameter.
     */
    
    void printVec(const vector<int>& v) {
        for (auto e: v) {
            cout << e << " ";
        }
        cout << endl;
    }
    
    
    int myswap(vector<int>& v, size_t i, size_t j) {
        int count = 0;
        while ((i < j) && (v[i] == j) && (v[j] == i)) {
            swap(v[i], v[j]);
            count++;
            i++;
            j--;
        }
        return count;
    }
    
    int check(const vector<int>& v) {
        for (size_t i = 0; i < v.size(); ++i) {
            if (v[i] != i) {
                return i;
            }
        }
        return -1;
    }
    
    void almostSorted(vector<int> arr) {
        size_t n = arr.size();
        vector<int> ix(n);
        iota(ix.begin(), ix.end(), 0);
        sort(
            ix.begin(),
            ix.end(),
            [&arr](size_t i, size_t j) { return arr[i] < arr[j]; }
        );
        // printVec(arr);
        // printVec(ix);
        
        int i = check(ix);
        if (i == -1) {
            cout << "yes" << endl;
            return;
        }
        
        size_t l = i;
        size_t r = ix[i];
        // cout << "l=" << l << " r=" << r << endl;
        
        int count = myswap(ix, l, r);
        // cout << "count=" << count << endl;
    
        i = check(ix);
        if (i == -1) {
            if (count == 1) {
                cout << "yes" << endl;
                cout << "swap " << l+1 << " " << r+1 << endl;
            } else {
                cout << "yes" << endl;
                cout << "reverse " << l+1 << " " << r+1 << endl;
            } 
        } else {
            cout << "no" << endl;
        }
        // printVec(ix);
    }