Käännöt

input/code.cpp: In function 'int inversions(std::vector<int>)':
input/code.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i = 0; i < vec.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
input/code.cpp:12:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for (int j = i+1; j < vec.size(); ++j) {
      |                           ~~^~~~~~~~~~~~
input/code.cpp: In function 'bool parity(std::vector<int>)':
input/code.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < vec.size(); ++i) {
      |                     ~~^~~~~~~~~~~~

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>

using namespace std;

int inversions(vector<int> vec) { //check inversions for k=4
    int inversions = 0;
    for (int i = 0; i < vec.size(); ++i) {
        for (int j = i+1; j < vec.size(); ++j) {
            if (vec[j] < vec[i]) {
                ++inversions;
            }
        }
    }
    //cout << "INV: " << inversions << endl;
    return inversions;
}

bool parity(vector<int> vec) {
    for (int i = 0; i < vec.size(); ++i) {
        if ((vec[i] & 1) != ((i + 1) & 1)) { // if a value and its index have mismatching parity, applicable for k=3, k=5
            return false;
        }
    }
    return true;
}

vector<int> bfs(vector<int> vec, int k) {
    vector<int> steps = {};

    int n = vec.size();

    vector<int> sorted = vec;
    sort(sorted.begin(), sorted.end());

    map<vector<int>, int> dist; // map of lists and their distances to start
    map<vector<int>, int> parent; // map of lists and the previous operation used to reach it

    queue<vector<int>> q; // bfs queue

    dist[vec] = 0; // the intial list is distance 0
    q.push(vec); // start with the initial list

    while (!q.empty()) { // checks all possibilities until it finds a solution
        vector<int> cur = q.front(); // checking the first value of queue
        q.pop();

        if (cur == sorted) { //end if sorted was found
            break;
        }

        for (int i = 0; i <= n - k; i++) { // for all possible reversals
            vector<int> next = cur;
            reverse(next.begin() + i, next.begin() + i + k);
            if (!dist.count(next)) { // if not already found
                dist[next] = dist[cur] + 1;
                parent[next] = i + 1;
                q.push(next); // add substates to queue to check
            }
        }
    }

    if (dist.count(sorted)) {
        for (vector<int> v = sorted; v != vec; v = v) {
            steps.push_back(parent[v]);
            reverse(v.begin() + parent[v] - 1, v.begin() + parent[v] - 1 + k);
        }
        reverse(steps.begin(), steps.end()); //reverse steps because they were traced back
    }

    return steps;
}

vector<int> solve(int n, int k, vector<int> vec) {
    vector<int> steps = {};

    int invs = inversions(vec);

    if (k == 3 || k == 5) {
        if (!parity(vec)) {
            //cout << "\nParity : unsolvable\n";
            return steps;
        }
    }

    if (k == 4) {
        if (invs & 1) { // number of inversions is odd : unsolvable with k=4
            //cout << "\nInversion parity with k=4 : unsolvable\n";
            return steps;
        }
        if (n <= 6) {
            //cout << "\nDoing bfs, short list w/ k=4\n";
            return bfs(vec, k);
        }
    }

    vector<int> moveset;

    bool run = true;
    int ceil = n-1; // ceiling based on sorted values
    int cur = n; // current value to sort
    int curi = -1; // current index of the value to sort
    while (run) {
        for (int i = ceil; i >= 0; --i) { // find largest unsorted value
            if (vec[i] == cur) {
                if (vec[i] == i + 1) {
                    --ceil;
                    --cur;
                    //cout << "\nSkip: " << cur;
                    if (ceil < k + 2 && k>3) {
                        //cout << "\nCEIL: " << ceil;
                        run = false;
                        break;
                    }
                    continue;
                }
                curi = i;
                //cout << "\nCur: " << cur << " & Cur i: " << curi;
                break; // found
            }
        }

        if (run == false) {
            break;
        }

        // sort the found value to its spot
        int targeti = cur - k; // 

        //cout << "\nTarget: " << targeti;

        while (curi != targeti) {
            int dist = targeti - curi;
            bool right = dist > 0;
            dist = abs(dist);

            //cout << "\nDistance: " << dist;
            //cout << "\nk-1: " << k-1;

            if (k - 1 <= dist) {
                steps.push_back(curi+1);
                reverse(vec.begin() + curi, vec.begin() + curi + k);
                curi += (k - 1);
                //cout << "\ncuri now " << curi;
                /*cout << "\n";
                for (int i : vec) {
                    cout << " " << i;
                }*/
            }
            else { // closer than k to target
                if (curi == 0) { // at the leftmost side, value has to be moved out first
                    steps.push_back(curi+1);
                    reverse(vec.begin() + curi, vec.begin() + curi + k);
                    curi += (k - 1);
                    /*cout << "\n";
                    for (int i : vec) {
                        cout << " " << i;
                    }*/
                    continue;
                }
                //cout << "\nclose to tgt";
                if (k == 4) {
                    if (right) {
                        for (int i = 0; i < dist; ++i) {
                            steps.push_back(curi);
                            reverse(vec.begin() + curi - 1, vec.begin() + curi + k-1);
                            ++curi;
                        }
                        //cout << "\ngoing tgt";
                    }
                    else { // edge case where value has ended up past the target
                        for (int i = 0; i < dist; ++i) {
                            steps.push_back(curi-1);
                            reverse(vec.begin() + curi - 2, vec.begin() + curi + k - 2);
                            --curi;
                        }
                        //cout << "\npast tgt";
                    }
                }
                else if (k == 5) {
                    if (right) {
                        steps.push_back(curi);
                        reverse(vec.begin() + curi - 1, vec.begin() + curi + k - 1);
                        curi += 2;
                        //cout << "\ngoing tgt";
                    }
                    else { // edge case where value has ended up past the target
                        steps.push_back(curi - 2);
                        reverse(vec.begin() + curi - 3, vec.begin() + curi + k - 3);
                        curi -= 2;
                        //cout << "\npast tgt";
                    }
                }
                break;
            }
        }

        //cout << "\nREACHED TARGET";

        /*cout << "\n";
        for (int i : vec) {
            cout << " " << i;
        }*/
        steps.push_back(curi + 1);
        reverse(vec.begin() + curi, vec.begin() + curi + k);

        //cout << "\nDONE";

        /*cout << "\n";
        for (int i : vec) {
            cout << " " << i;
        }*/


        if (is_sorted(vec.begin(), vec.end())) {
            break;
        }
    }

    /*cout << "\nFINAL LIST :: \n";
    cout << "\n";
    for (int i : vec) {
        cout << " " << i;
    }*/

    if (!is_sorted(vec.begin(), vec.end())) {
        if (k > 3) { // find solution to unsorted part using bfs
            vector<int> subvec(vec.begin(), vec.begin() + k + 2);
            vector<int> substeps = bfs(subvec, k);
            if (substeps.size() > 0) {
                steps.insert(steps.end(), substeps.begin(), substeps.end());
            }
            else {
                steps = {};
            }
        }
    }
    //cout << "\n";
    return steps;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    // take inputs
    int n, k;
    cin >> n;
    cin >> k;

    vector<int> vec(n);

    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    // end of inputs

    if (is_sorted(vec.begin(), vec.end())) { //already sorted, return YES 0
        cout << "YES\n" << 0;
        return 0;
    }

    vector<int> steps = solve(n, k, vec);

    if (steps.size() > 0) {
        cout << "YES" << "\n" << steps.size() << "\n";
        for (int step : steps) cout << step << " ";
        cout << "\n";
    }
    else {
        cout << "NO" << "\n";
    }

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

Test 19

Group: 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: ACCEPTED

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

Test 29

Group: 4

Verdict: ACCEPTED

Test 30

Group: 4

Verdict: ACCEPTED

Test 31

Group: 4

Verdict: ACCEPTED

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: ACCEPTED

Test 34

Group: 4

Verdict: ACCEPTED