Luogu

LOJ

分析

假设已经排好了 $1\sim i$，考虑如何把 $i+1$ 放到 $i$ 后面。可以构造出这样的方案：

• 首先用 ka 把 $i+1$ 移到最前面。
• 重复使用 2a 1b 把 $i$ 后面的元素两个两个地移到 $i+1$ 和 $1$ 之间。
• 如果最后 $i+1$ 后面还有一个元素，使用 1a 2b 把它移到 $i+1$ 和 $1$ 之间。

这样子有一个问题，即当 $n-1$ 在最前面、$n$ 在最后面（即 $n-1,1,2,\cdots,n-2,n$）的时候我们用 1a 2b 会把 $n$ 放到 $1,2$ 之间去，然后就 GG 了。所以可以想到另外一种构造方案：

• 首先用 ka 把 $n$ 移到最前面，变成 $n,n-1,1,2,\cdots,n-2$。
• 重复使用 2a 1b 将序列变为 $n,1,2,\cdots,n-1$。

但是这个方案在 $n$ 为奇数时是无效的，所以这种情况下无解。

可以用 std::deque 模拟整个过程。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define mp make_pair
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int n;
deque<int> a;
vector<pair<int,int>> sta,ans;

void moveA(int c) {
    if (sta.empty()||sta.back().second!='a') sta.emplace_back(mp(c,'a'));
    else sta.back().first+=c;
    for (int i=1;i<=c;++i) a.push_front(a.back()),a.pop_back();
}
void moveB(int c) {
    if (sta.empty()||sta.back().second!='b') sta.emplace_back(mp(c,'b'));
    else sta.back().first+=c;
    for (int i=1,t;i<=c;++i) t=a[0],a[0]=a[2],a[2]=a[1],a[1]=t;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a.push_back(read());
    if (n==1) { puts("0"); return 0; }
    if (n==2) { puts(a[0]==1?"0":"1\n1a"); return 0; }
    for (int i=2;i<=n-2;++i) {
        for (int j=1;j<n;++j)
            if (a[j]==i) { moveA(n-j); break; }
        while (a[n-1]!=i-1) {
            if (a[n-2]!=i-1) moveA(2),moveB(1);
            else moveA(1),moveB(2);
        }
    }
    for (int i=1;i<n;++i)
        if (a[i]==n) { moveA(n-i); break; }
    if (a[1]==n-1) {
        if (n&1) { puts("NIE DA SIE"); return 0; }
        while (a[n-1]!=n-1) moveA(2),moveB(1);
    }
    moveA(n-1);
    for (auto i:sta) {
        if (i.second=='a') i.first%=n;
        else i.first%=3;
        if (i.first) ans.emplace_back(i);
    }
    printf("%d\n",ans.size());
    for (auto i:ans) printf("%d%c ",i.first,i.second);
    return 0;
}