Käännöt

input/code.cpp: In function 'std::vector<int> bubble(std::vector<int>&)':
input/code.cpp:12:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for(int i = 0; i < unsorted.size()-1; i++)
      |                        ~~^~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'std::vector<int> quadruple(std::vector<int>&)':
input/code.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         while(index != unsorted.size()-1){
      |               ~~~~~~^~~~~~~~~~~~~~~~~~~~
input/code.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i = 0; i <= unsorted.size()-4; i++){
      |                        ~~^~~~~~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
vector<int> bubble(vector<int>& unsorted){
    vector<int> ans;
    bool loop = true;
    while(loop){
        loop = false;
        for(int i = 0; i < unsorted.size()-1; i++)
            if(unsorted[i] > unsorted[i+1]){
                swap(unsorted[i], unsorted[i+1]);
                ans.push_back(i+1);
                loop = true;
            }
    }
    return ans;
}

vector<int> triple(vector<int>& unsorted){
    vector<int> ans;
    int highest_not_sorted = unsorted.size();

    while(highest_not_sorted > 0){
        auto index = find(unsorted.begin(), unsorted.end(), highest_not_sorted) - unsorted.begin();
        
        if(abs(index - highest_not_sorted)%2 == 0)
            return vector<int>(1000001);
        
        for(int i = index; i < highest_not_sorted-1; i += 2){
            swap(unsorted[i], unsorted[i+2]);
            ans.push_back(i+1);
        }
        highest_not_sorted--;
    }

    return ans;
}

void swap(vector<int>& input, int index){
    swap(input[index], input[index+3]);
    swap(input[index+1], input[index+2]);
}

vector<int> quadruple(vector<int>& unsorted){
    vector<int> ans;

    while(unsorted.size() > 6){
        int index = find(unsorted.begin(), unsorted.end(), unsorted.size()) - unsorted.begin();
        
        while(index != unsorted.size()-1){
            while((unsorted.size()-1 - index)%3 != 0){
                if(index == 0){
                    swap(unsorted, index);
                    ans.push_back(index);
                    index += 3;
                }

                else if((unsorted.size()-1 - index) < 3){
                    swap(unsorted, index-2);
                    ans.push_back(index-2);
                    index--;
                } else {
                    swap(unsorted, index-1);
                    ans.push_back(index-1);
                    index++;
                }
            }
            swap(unsorted, index);
            ans.push_back(index);
            index += 3;
        }
        unsorted.pop_back();
    }

    set<vector<int>> brute;
    vector<pair<vector<int>, vector<int>>> queue;
    queue.push_back(make_pair(unsorted, vector<int>()));

    auto sorted = unsorted;
    sort(sorted.begin(), sorted.end());

    while(!queue.empty()){
        auto vec = queue[0].first;
        auto steps = queue[0].second;
        queue.erase(queue.begin());

        if(vec == sorted){
            ans.insert(ans.end(), steps.begin(), steps.end());
            return ans;
        }
        for(int i = 0; i <= unsorted.size()-4; i++){
            auto vec_copy = vec;
            auto steps_copy = steps;
            swap(vec_copy, i);
            steps.push_back(i);
            if(brute.find(vec_copy) == brute.end()){
                brute.insert(vec_copy);
                queue.push_back(make_pair(vec_copy, steps_copy));
            }
        }
    }

    return vector<int>(1000001);
}
 
int main(){
    int n, k;
    cin >> n >> k;
 
    vector<int> unsorted(n);
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        unsorted[i] = a;
    }
    
    vector<int> ans;
    if(k == 2)
        ans = bubble(unsorted);
    
    else if(k == 3)
        ans = triple(unsorted);

    else if(k == 4)
        ans = quadruple(unsorted);
    
    if(ans.size() <= 1000000){
        cout << "YES\n" << ans.size()+2 << "\n1 1 ";
        for(auto c : ans)
            cout << c << " ";
    }
    else
        cout << "NO";
}

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

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

Test 33

Group: 4

Verdict: WRONG ANSWER

Test 34

Group: 4

Verdict: WRONG ANSWER