Käännöt

#include <bits/stdc++.h>
 
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);
}

vector<int> compress(vector<int> a) {
    vector<int> b = a;

    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());

    for (int &x : a)
        x = int(lower_bound(b.begin(), b.end(), x) - b.begin()) + 1;

    return a;
}


vector<int> solve2(int n, int k, vector<int> a) {
    queue<vector<int>>  q;
    q.push(a);

    map<vector<int>, int> d;
    d[a] = 0;

    map<vector<int>, vector<int>> prev;
    
    map<vector<int>, int> prev_op;
    prev_op[a] = -1;

    while (!q.empty()) {
        vector<int> v = q.front();
        q.pop();

        if (is_sorted(v.begin(), v.end())) {
            //cout << d[v] << '\n';
            
            vector<int> ops;
            while (prev_op[v] != -1) {
                ops.push_back(prev_op[v] + 1);
                v = prev[v];
            }

            reverse(ops.begin(), ops.end());

            return ops;
        }

        for (int i = 0; i < n - (k - 1); ++i) {
            vector<int> next = v;
            reverse(next.begin() + i, next.begin() + i + k);
            if (!d.count(next) || d[next] > d[v] + 1) {
                q.push(next);
                prev[next] = v;
                prev_op[next] = i;
                d[next] = d[v] + 1;
            }
        }
    }

    return vector<int> ();
}

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;

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

    if (is_sorted(a.begin() + 1, a.end())) {
        cout << "YES" << '\n';
        cout << res.size() << '\n';
        for (auto i : res) {
            cout << i << ' ';
        }
        return;
    }

    map<vector<int>, vector<int>> mp;
    mp[{1, 2, 3, 4, 5, 7, 8, 6}] = {3, 2, 5, 2, 4, 5, 2, 4};
    mp[{1, 2, 3, 4, 5, 8, 6, 7}] = {4, 2, 5, 4, 2, 5, 2, 3};
    mp[{1, 2, 3, 4, 6, 5, 8, 7}] = {3, 4, 3, 5, 3, 4, 3};
    mp[{1, 2, 3, 4, 6, 7, 5, 8}] = {2, 1, 4, 1, 3, 4, 1, 3};
    mp[{1, 2, 3, 4, 6, 8, 7, 5}] = {2, 1, 4, 5, 4, 3, 1, 2};
    mp[{1, 2, 3, 4, 7, 5, 6, 8}] = {3, 1, 4, 3, 1, 4, 1, 2};
    mp[{1, 2, 3, 4, 7, 6, 8, 5}] = {3, 4, 3, 2, 5, 2, 5, 2};
    mp[{1, 2, 3, 4, 7, 8, 5, 6}] = {3, 2, 3, 5, 3, 2, 3};
    mp[{1, 2, 3, 4, 8, 5, 7, 6}] = {2, 1, 3, 4, 5, 4, 1, 2};
    mp[{1, 2, 3, 4, 8, 6, 5, 7}] = {2, 4, 2, 5, 4, 3, 2, 4};
    mp[{1, 2, 3, 4, 8, 7, 6, 5}] = {5};

    vector<int> lst;
    for (int i = n - 7; i <= n; ++i) {
        lst.push_back(a[i]);
    }

    compress(lst);

    if (mp.count(lst)) {
        for (auto i : mp[lst]) {
            rev(i + (n - 8), k, a, pos, res);
        }
    }

    if (is_sorted(a.begin() + 1, a.end())) {
        cout << "YES" << '\n';
        cout << res.size() << '\n';
        for (auto i : res) {
            cout << i << ' ';
        }
        return;
    }

    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: WRONG ANSWER

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: ACCEPTED

Test 19

Group: 3

Verdict: WRONG ANSWER

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: WRONG ANSWER

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: ACCEPTED

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: ACCEPTED

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: ACCEPTED

Test 34

Group: 4

Verdict: WRONG ANSWER