乱搞
非正解写法。分类讨论各种情况。
- 降序排序
对应交换即可
- 数组个数小
直接考虑相邻的交换
- 其他都看做随机数据
考虑结合前面情况，很容易想到，先把数组变成一个尽量有序的数组（每个元素和自己正确的位置相差不大）。最后再多次相邻交换，使得每个元素都在正确位置。
把数组变成一个尽量有序的过程，很容易想到希尔排序。我们做一个类似希尔排序的操作，每次设定\(d\)，使\(i\)和\(i+d\)交换，然后\(d/=2\)。多次进行这样的操作，但是发现每次都有些位置\(j\)一直是和\(j-d\)交换的，在这些位置不少于某个值的时候，我们考虑让\(j\)和\(j+d\)交换，这样我们就得到了个尽量有序的数组。
很好的过样例，submit WA。剩下的就是调参的内容了。写一份check代码。打印每次选择的有序对时，成功交换的比例，调参使得前几次交换比例高，后面交互比例为0。你问我正确性？我也不知道，我只能说本地随机一百组数据都是可以通过的。
细节：
- 特判\(n=0,1\)
- 注意每个有序对\((x,y)\)，\(x\)都小于\(y\)
- 一个位置一次交换只能出现一次
- \(d\)的选择不能每次都是\(n\)的因数，不然有些值一直在某些固定位置选择，并且不动。
vector<pii>ans[205];
bool vis[MAXN];
void solve() {
n = read();
if (n == 1) return printf("0\n"), void();
if (n == 2) return printf("1\n1 0 1\n"), void();
for (int i = 0, j = n - 1; i < j; ++i, --j)
ans[1].push_back({i, j});
m = 2;
if (n <= 10) {
for (; m <= 200; ++m) {
for (int i = 1 - (m & 1); i + 1 < n; i += 2) {
int x = i, y = i + 1;
if (x > y)swap(x, y);
ans[m].push_back({x, y});
}
}
} else {
for (int k = 0; k < 24; ++k) {
for (int len = 10000 >> (k + 1); len >= 5; len >>= 1) {
if (len > n / 2)continue;
memset(vis, 0, sizeof(vis));
for (int i = 0; i + len < n; ++i) {
int x = i, y = i + len;
if (x > y)swap(x, y);
if (!vis[x] && !vis[y]) {
vis[x] = vis[y] = 1;
ans[m].push_back({x, y});
}
}
++m;
if (len >= n / 10)continue;
memset(vis, 0, sizeof(vis));
for (int i = len; i + len < n; ++i) {
int x = i, y = i + len;
if (x > y)swap(x, y);
if (!vis[x] && !vis[y]) {
vis[x] = vis[y] = 1;
ans[m].push_back({x, y});
}
}
++m;
}
}
for (; m <= 200; ++m) {
for (int i = 1 - (m & 1); i + 1 < n; i += 2) {
int x = i, y = i + 1;
if (x > y)swap(x, y);
ans[m].push_back({x, y});
}
}
}
printf("%d\n", m - 1);
for (int i = 1; i < m; ++i, enl) {
printf("%d ", ans[i].size());
for (auto& [x, y] : ans[i])printf("%d %d ", x, y);
}
}