P3516 [POI2011]PRZ-Shift

8
1 2 3 4 5 6 8 7

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=2010;
int n,a[N<<1],b[N],s[5],p[N<<1],h;
#define P pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<P> Ans,F;
I void Move(CI t,CI x){//模拟移动，把他拉成一个环，做到 O(1) 模拟。
    RI i;if(t==1) (h+=n-x)%=n;
    else{
        for(i=3-x+1;i<=3;i++) p[i-(3-x)]=a[h+i];for(i=1;i<=3-x;i++) p[x+i]=a[h+i];
        for(i=1;i<=3;i++) a[h+i]=p[i];for(i=1;i<=3;i++) a[(h+n+i)%(2*n)]=p[i];
    }
}
int main(){
    RI i,j,k,t;for(read(n),i=1;i<=n;i++) read(a[i]),b[i]=a[i];for(i=n+1;i<=2*n;i++) a[i]=a[i-n];
    for(i=1;i<=n-2;i++){
        for(j=1;j<=n;j++) if(a[h+j]==i) break ; 
        if(j==i) continue ;
        k=i-1,!k&&(k=n),t=0;if(j>1) Ans.push_back(MP(1,n-j+1)),k+=n-j+1,Move(1,n-j+1);
        k%=n,!k&&(k=n),swap(j,k);W(j+2<=n) Ans.push_back(MP(1,2)),Move(1,2),Ans.push_back(MP(2,1)),Move(2,1),j+=2,t++;
        if(j+1<=n) Ans.push_back(MP(1,1)),Move(1,1),Ans.push_back(MP(2,2)),Move(2,2),j++,t++;//注意判断边界
        Ans.push_back(MP(1,i-1)),Move(1,i-1);
    }for(i=n-1;i<=n;i++) s[i-(n-2)]=a[h+i]-(n-2);for(i=1;i<=2;i++) a[i]=s[i];if(a[1]==2&&a[2]==1){
        if(n&1) return puts("NIE"),0;
        for(Ans.push_back(MP(1,2)),i=n/2-1;i>=1;i--) Ans.push_back(MP(1,2)),Ans.push_back(MP(2,1));Ans.push_back(MP(1,n-1));//如果出现最后两个不符情况
    }for(i=0;i<Ans.size();){
        j=i+1;W(j<Ans.size()&&Ans[j].fi==Ans[i].fi) Ans[i].se+=Ans[j].se,j++;if(Ans[i].fi&1) Ans[i].se%=n;else Ans[i].se%=3;
        Ans[i].se&&(F.push_back(Ans[i]),0);i=j;//合并输出
    }writeln(F.size());for(auto i:F) write(i.se),pc(i.fi+'a'-1),pc(' ');
    return pc('\n'),0;
}