Käännöt

#include <bits/stdc++.h>
#define int long long

using namespace std;

void init_code() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

bool is_ok(int j, int i, int n, int k) {
    if (j < 1 || (j + (k - 1)) > n || j < i) {
        return false;
    }

    return true;
}

void rev(int i, int k, vector<int>& a, vector<int>& pos, vector<int>& res) {
    reverse(a.begin() + i, a.begin() + i + k);

    for (int ik = 0; ik <= k - 1; ++ik) {
        pos[a[i + ik]] = i + ik;
    }

    res.push_back(i);
}

void solve() {
    int n, k;
    cin >> n >> k;

    vector<int> a(n + 1, -1), pos(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        pos[a[i]] = i;
    }

    vector<int> res;

    for (int i = 1; i <= n - (k - 1); ++i) {
        if (a[i] == i) {
            continue;
        }

        int j = pos[i];
        
        vector<int> fix;
        if ((j - i) % (k - 1) != 0) {
            queue<pair<vector<int>, int>> q;    
            q.push({vector<int> (), j});

            int x = 0;
            while (!q.empty() && x <= 100) {
                vector<int> op = q.front().first;
                int cur_j = q.front().second;

                q.pop();

                if (cur_j < i) {
                    continue;
                }

                if ((cur_j - i) % (k - 1) == 0) {
                    fix = op;
                    break;
                }

                for (int it = j - (k - 1); it <= j + (k - 1); ++it) {
                    if (is_ok(it, i, n, k)) {
                        op.push_back(it);
                        int new_j = it + k + 1 - abs(j - it);
                        q.push({op, new_j});
                        op.pop_back();
                        x++;
                    }
                }
            }
        }
        
        for (auto it : fix) {
            rev(it, k, a, pos, res);
        }  
        
        if ((j - i) % (k - 1) == 0) {
            while (j != i) {
                rev(j - (k - 1), k, a, pos, res);
                j -= (k - 1);
            }
        } else {
            cout << "NO" << '\n';
            return;
        }
    }
    
    if (is_sorted(a.begin(), a.end())) {
        cout << "YES" << '\n';
        cout << res.size() << '\n';
        for (auto i : res) {
            cout << i << ' ';
        }
    } else {
        cout << "NO" << '\n';
    }
}

signed main() {
    init_code();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: WRONG ANSWER

Test 19

Group: 3

Verdict: WRONG ANSWER

Test 20

Group: 3

Verdict: WRONG ANSWER

Test 21

Group: 3

Verdict: WRONG ANSWER

Test 22

Group: 3

Verdict: WRONG ANSWER

Test 23

Group: 3

Verdict: WRONG ANSWER

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: WRONG ANSWER

Test 26

Group: 4

Verdict: ACCEPTED

Test 27

Group: 4

Verdict: ACCEPTED

Test 28

Group: 4

Verdict: WRONG ANSWER

Test 29

Group: 4

Verdict: WRONG ANSWER

Test 30

Group: 4

Verdict: WRONG ANSWER

Test 31

Group: 4

Verdict: WRONG ANSWER

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: WRONG ANSWER

Test 34

Group: 4

Verdict: WRONG ANSWER