[评测链接](https://www.luogu.org/record/show?rid=10537809)
代码 :
```cpp
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int p[2100], n, tag, cnt, q[2100];
int opt[41000000], ans[4100000];
char a = 'a', b = 'b';
inline int pos(int x) {return (p[x]-1+tag)%n+1; }
inline int get(int x) {return ((x-tag-1)%n+n)%n+1;}
inline void reverse() {
int s1=get(1), s2=get(2), s3=get(3);
int x=q[s1], y=q[s2], z=q[s3];
int t=p[x];
p[x]=p[y], p[y]=p[z], p[z]=t;
q[p[x]]=x, q[p[y]]=y, q[p[z]]=z;
}
inline void print(int k, char c) {
//printf("%d\n", k);
if(k >= n) k%=n;
if(k) {
cnt ++;
opt[cnt] = c - 'a';
ans[cnt] = k;
if(c == a) tag += k;
if(c == b) while(k--) reverse();
}
}
inline void move(int x) {
if(pos(x) != 1)
print(n-pos(x)+1, a);
}
inline void test() {
printf("%d %d %d %d\n", pos(1), pos(2), pos(3), pos(4));
printf("%d %d %d %d\n", q[1], 2[q], 3[q], 4[q]);
}
inline void work() {
//printf("%d %d\n", pos(1), pos(2));
for(int i = 2; i <= n-2; i ++ ) {
if(pos(i) != pos(i-1)+1) {
move(i);
int lst = n-pos(i-1);
for(int k = 2; k <= lst; k += 2) print(2, a), print(1, b);
if(lst & 1) print(1, a), print(2, b);
move(1);
}
}
if(pos(n-1) == n-1) return;
if(n&1) puts("NIE DA SIE"), exit(0);
for(int i = 1; i <= (n-2)/2; i ++ ) {
move(n-1);
print(2, b);
}
if(pos(1) != 1)move(1);
}
inline void init() {
bool flag = 1;
scanf("%d", &n);
for(int i = 1, x; i <= n; i ++ ) {
scanf("%d", &x),
p[x] = i;
q[i] = x;
if(i != x) flag = 0;
}
if(flag) puts("0"), exit(0);
if(n == 2) printf("1\n1a"),exit(0);
}
inline void getans() {
int tot = 0, now = -1;
int k = 0;
for(int i = 1; i <= cnt; i ++ ) {
if(opt[i] != now) {
tot++, now = opt[i];
}
}
if(tot == 0) return ;
now = -1; k = 0;
tot = 0;
for(int i = 1; i <= cnt; i ++ ) {
if(opt[i] != now) {
if(k%n && now != -1) ans[++tot] = k%n, opt[tot] = now;
now = opt[i]; k = ans[i];
}
else k += ans[i];
}
ans[++tot] = k%n, opt[tot] = now;
printf("%d\n", tot);
for(int i = 1; i <= tot; i ++ ) printf("%d%c ", ans[i], opt[i]+'a');
}
int main() {
init();
work();
getans();
}
```
by ToBiChi @ 2018-10-22 20:18:03
@[ToBiChi](/space/show?uid=69014) "NIE DA SIE"是什么东西
by Itst @ 2018-10-22 20:18:47
？？？
by 已注销%Jm9VScx @ 2018-10-22 20:19:28
有关 $N = 2$ 的特判 :
若原序列已经是有序了, 则在之前就 `return` 了,
否则需要特判
by ToBiChi @ 2018-10-22 20:19:59
@[ToBiChi](/space/show?uid=69014)
无解的话输出“NIE”
无解的话输出“NIE”
无解的话输出“NIE”
by Itst @ 2018-10-22 20:21:56
关于 NA DA SIE :
POI 原题数据/题面即为 NA DA SIE
@[Itst](/space/show?uid=96296)
需要我给你提供截图/链接么
by ToBiChi @ 2018-10-22 20:23:35
@[ToBiChi](/space/show?uid=69014) 这题的spj是 cn：苏卿念dalao 写的，按照洛谷的题面描述是应该输出NIE
当然loj是输出NIE DA SIE
在转移提交记录的时候还是要看一看有一些区别的
by xzyxzy @ 2018-10-22 20:25:25
贵谷不是很尊重原题要求么 ?
提供zyl原话链接 : [链接](https://www.luogu.org/discuss/show?postid=36059)
为按照原题要求, 一道大家都申请开大内存的题, 直接把内存开的更小
by ToBiChi @ 2018-10-22 20:26:56
@[ToBiChi](/space/show?uid=69014) 额……这个spj是我加的qwq
by 小可爱三岁七 @ 2018-10-22 20:27:14
@[ToBiChi](/space/show?uid=69014) 目前出了点锅……正在修的…修好了会rej的，
by 小可爱三岁七 @ 2018-10-22 20:27:41