Käännöt

input/code.cpp: In function 'void solve_2(vl&, vl&, ll)':
input/code.cpp:17:10: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   17 |     bool b;
      |          ^
input/code.cpp: In function 'void solve_3(vl&, vl&, ll)':
input/code.cpp:59:14: warning: unused variable 'b' [-Wunused-variable]
   59 |         bool b = (p[i] != i);
      |              ^
input/code.cpp: At global scope:
input/code.cpp:101:29: error: 'vitem' has not been declared
  101 | void build_tree(ll n, ll k, vitem &v, sstr &ss)
      |                             ^~~~~
input/code.cpp:101:39: error: 'sstr' has not been declared
  101 | void build_tree(ll n, ll k, vitem &v, sstr &ss)
      |                                       ^~~~
input/code.cpp: In function 'void build_tree(ll, ll, int&, int&)':
input/code.cpp:107:7: error: request for member 'push_back' in 'v', which is of non-class type 'int'
  107 |     v.push_back({s,{-1,-1}});
      |       ^~~~~~~~~
input/code.cpp:109:8: error: request...

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;


void outp(vl &a, ll n)
{
    for(ll i = 1; i <= n; i++)
        cout << a[i] << " ";
}

void solve_2(vl &a, vl &p, ll n)
{
    cout << "YES\n";
    ll p1, p2, i;
    bool b;
    vl op;
    for(i = n; i >= 1; i--)
    {
        b = (p[i] != i);
        while(p[i] > i)
        {
            p1 = p[i]; p2 = p1 - 1;
            op.push_back(p2);
            p[a[p2]] = p1;
            swap(a[p1], a[p2]);
            p[i]--;
        }
        while(p[i] < i)
        {
            p1 = p[i]; p2 = p1 + 1;
            op.push_back(p1);
            p[a[p2]] = p1;
            swap(a[p1], a[p2]);
            p[i]++;
        }
    }
    cout << op.size() << '\n';
    for(auto x : op)
        cout << x << " ";
    cout << "\n";
}

void solve_3(vl &a, vl &p, ll n)
{
    ll i;
    for(i = 1; i <= n; i++)
        if ((p[i] - i) % 2)
        {
            cout << "NO\n";
            return;
        }
    cout << "YES\n";
    ll p1, p2;
    vl op;
    for(i = n; i >= 1; i--)
    {
        bool b = (p[i] != i);
        while(p[i] > i)
        {
            p1 = p[i], p2 = p1 - 2;
            op.push_back(p2);
            p[a[p2]] = p1;
            swap(a[p1], a[p2]);
            p[i] = p2;
        }
        while(p[i] < i)
        {
            p1 = p[i], p2 = p1 + 2;
            op.push_back(p1);
            p[a[p2]] = p1;
            swap(a[p1], a[p2]);
            p[i] = p2;
        }
//        if (b)
//        {
//            outp(a,n); cout << "\n";
//            outp(p,n); cout << "\n";
//        }
    }
    cout << op.size() << "\n";
    for(auto x : op)
        cout << x << " ";
    cout << "\n";
}

void rev(vl &a, vl &p, ll n, ll k, ll stpos, vl &op)
{
    ll ii, jj, t;
    for (ii = stpos, jj = stpos + k - 1; ii < jj; ii++, jj--)
    {
        t = p[a[ii]];
        p[a[ii]] = p[a[jj]];
        p[a[jj]] = t;
        swap(a[ii], a[jj]);
    }
    op.push_back(stpos);
}

void build_tree(ll n, ll k, vitem &v, sstr &ss)
{
    queue <ll> q;
    string s(n, '1'), t, r;
    ll i, parent;
    iota(s.begin(), s.end(), '1');
    v.push_back({s,{-1,-1}});
    q.push(0);
    ss.insert(s);
    while(!q.empty())
    {
        parent = q.front();
        r = v[parent].first;
        // cout << r << " " << "\n";
        q.pop();
        for(i = 0; i <= n - k; i++)
        {
            t = r;
            reverse(t.begin()+i, t.begin()+i+k);
            if (ss.find(t) == ss.end())
            {
                ss.insert(t);
                v.push_back({t, {parent, i}});
                q.push(v.size()-1);
            }
        }
    }
}

void view_tree(vitem &v)
{
    cout << v.size() << "\n";
    for (ll i = 0; i < v.size(); i++)
        cout << i << " " << v[i].first  << setw(4) << v[i].second.first << setw(4) << v[i].second.second << "\n";
}

void solve_4(vl &a, vl &p, ll n)
{
    ll i, j, m;
    string s;
    vl op;
    for (i = n; i >= 7; i--)
    {
        if (p[i] < i)
        {
            if (p[i] == i - 2)
                rev(a, p, n, 4, p[i]-2, op);
            else
                if (p[i] == i-1)
                    rev(a, p, n, 4, p[i]-3, op);

            if (p[i] < 3)
                rev(a, p, n, 4, p[i], op);
            j = (i - p[i]) % 3;
            rev(a, p, n, 4, p[i]-j, op);
            outp(a, n); cout << "\n";
            outp(p, n); cout << "\n";
            while(p[i] < i)
                rev(a, p, n, 4, p[i], op);
        }
    }
//    outp(a, n); cout << "\n";
//    outp(p, n); cout << "\n";
    m = min(n, 6ll);
    for (i = 1; i <= m; i++)
        s += char(a[i] + '0');
    vitem v;
    sstr ss;
    build_tree(m, 4, v, ss);
    for (i = 0; i < v.size(); i++)
    {
        auto str = v[i].first;
        if (str == s)
            break;
    }
    if (i == v.size())
        cout << "NO\n";
    else
    {
        // view_tree(v);
        j = i;
        while(j > 0)
        {
            op.push_back(v[j].second.second);
            j = v[j].second.first;
        }
        print_op(op);
    }
}

int main()
{
    ll n, k, i;
    cin >> n >> k;
    vl a(n+1), p(n+1);
    for(i = 1; i <= n; i++)
        cin >> a[i];
    for(i = 1; i <= n; i++)
        p[a[i]] = i;
    if(k == 2)
        solve_2(a, p, n);
    else
        if(k == 3)
            solve_3(a, p, n);
        else
            if(k == 4)
                solve_4(a, p, n);
    return 0;
}