Käännöt

input/code.cpp: In function 'bool brute4(std::vector<int>)':
input/code.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; i < a.size(); ++i) g &= a[i] == i+1;
      |                         ~~^~~~~~~~~~
input/code.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for (int i = 0; i < a.size()-3; ++i) {
      |                         ~~^~~~~~~~~~~~

#include <bits/stdc++.h>

#define MODE 1

#if MODE
#define debug(x) cout << #x << ": " << x << endl
#define log(x) cout << x << endl
#define test(x) x
#else
#define debug(x)
#define log(x)
#define test(x)
#endif

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define X real()
#define Y imag()

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using P = complex<ll>;

const ll M = 1000000007; // 998244353

map<vector<int>, int> mov;
vector<int> bruteans;

bool brute4(vector<int> a) {
    queue<vector<int>> bfs;
    bfs.push(a);
    mov[a] = -1;
    while (bfs.size()) {
        a = bfs.front();
        bfs.pop();
        bool g = 1;
        for (int i = 0; i < a.size(); ++i) g &= a[i] == i+1;
        if (g) {
            while (mov[a] != -1) {
                bruteans.push_back(mov[a]);
                reverse(a.begin()+mov[a], a.begin()+mov[a]+4);
            }
            reverse(all(bruteans));
            return 1;
        }
        for (int i = 0; i < a.size()-3; ++i) {
            reverse(a.begin()+i, a.begin()+i+4);
            if (!mov.count(a)) {
                mov[a] = i;
                bfs.push(a);
            }
            reverse(a.begin()+i, a.begin()+i+4);
        }
    }
    return 0;
}

void solve() {
    int n, k;
    cin >> n >> k;
    
    vector<int> v(n);
    for (int &i : v) cin >> i;
    
    vector<int> ans;
    if (k == 2) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n-1; ++j) if (v[j] > v[j+1]) {
                ans.push_back(j);
                swap(v[j], v[j+1]);
            }
        }
    } else if (k == 3) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j+2 < n; j += 2) if (v[j] > v[j+2]) {
                ans.push_back(j);
                swap(v[j], v[j+2]);
            }
        }
        
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j+2 < n; j += 2) if (v[j] > v[j+2]) {
                ans.push_back(j);
                swap(v[j], v[j+2]);
            }
        }
        
        for (int i = 0; i < n; ++i) if (v[i] != i+1) {
            cout << "NO\n";
            return;
        }
    } else if (k == 4) {
        if (n == 5) {
            if (brute4(v)) ans = bruteans;
            else {
                cout << "NO\n";
                return;
            }
        } else {
            for (int i = n; i > 6; --i) {
                int j = 0;
                while (v[j] != i) ++j;
                if (j == i-1) continue;
                if (j == 0) {
                    ans.push_back(0);
                    reverse(v.begin()+0, v.begin()+4);
                    j += 3;
                }
                while (j > i-4) {
                    ans.push_back(j-2);
                    reverse(v.begin()+j-2, v.begin()+j+2);
                    --j;
                }
                while (j < i-4) {
                    ans.push_back(j-1);
                    reverse(v.begin()+j-1, v.begin()+j+3);
                    ++j;
                }
                
                ans.push_back(i-4);
                reverse(v.begin()+i-4, v.begin()+i);
            }
            
            vector<int> a(6);
            for (int i = 0; i < 6; ++i) a[i] = v[i];
            if (brute4(a)) for (int i : bruteans) ans.push_back(i);
            else {
                cout << "NO\n";
                return;
            }
        }
    } else {
        
    }
    
    cout << "YES\n";
    cout << ans.size() << '\n';
    for (int p : ans) cout << p+1 << ' ';
    cout << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int t = 1;
    if (t == 0) 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: 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: 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