C毕业照

题意理解

念一次abcde， 出列顺序是abcde，归队顺序是出列顺序的逆序，因此是edcba。此时念重复一次口令，edcba会依次进入abcde。

因此口令的作用是让这些位置的人按照口令的顺序互换。a↔e，b↔d。

Hint1

最后要达成升序，因此每个数字都有一个终点位置。我们从这个数字的最初位置向这个数字的目标位置连边。这样就得到了若干个环。

如果环的大小为1，说明这是一个自环，数字本就在自己的位置上。

如果换的大小为2，说明环上的两个点互换一下就能达到正确位置。

如果环的大小在2以上，我们考虑如何让环变小。

看到这里可以自己先思考一下如何割/缩环。

Hint2

假设我们有一个如图所示的换，代表当前位置1上的数要去位置2，当前位置2上的数要去位置3，以此类推。

此时我们对调1和3。位置1上的数变成了刚才位置3上的数，应该指向4；位置3上的数变成了位置1上的数，应该指向2。

因此这个图变成了这样。

下一步调换6和4，以此类推。

不论环上的点是奇数个还是偶数个，都能按照这个方法将大环分解为若干大小不超过2的小环。

最后将所有大小为2的小环对调即可。

因此最多需要2次操作。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 3005;

int n;

struct NODE {
	int pos;
	int to;
}node[N];

bitset<N>flag;

deque<int>ans1, ans2;
deque<int>cir;

void out() {
	cout << ans1.size() * 2 << endl;
	while (!ans1.empty()) {
		cout << ans1.front() << ' ';
		ans1.pop_front();
	}
	while (!ans2.empty()) {
		cout << ans2.back() << ' ';
		ans2.pop_back();
	}
	cout << endl;
}

void Solve() {
	cin >> n;
	
	for (int i = 1; i <= n; ++i) {
		cin >> node[i].to;
		node[i].pos = i;
	}
	
	sort(node + 1, node + n + 1, [](NODE x, NODE y){return x.to < y.to;});
	for (int i = 1; i <= n; ++i) {
		node[i].to = i;
	}
	sort(node + 1, node + n + 1, [](NODE x, NODE y){return x.pos < y.pos;});
	
	for (int i = 1; i <= n; ++i) {
		if (node[i].to == i) {
			flag[i] = 1;
		}
	}
	
	//全是自环
	if (flag.count() == (unsigned long long)n) {
		cout << 0 << endl;
		return;
	}
	
	//找环，初步割环
	for (int i = 1; i <= n; ++i) {
		if (flag[i]) continue;
		cir.clear();
		int head = i, u = i;
		do {
			flag[u] = 1;
			cir.push_back(u);
			u = node[u].to;
		} while (u != head);
		
		if (cir.size() < 3) continue;
		
		cir.pop_front();
		while (cir.size() >= 2) {
			ans1.push_back(cir.front());
			ans2.push_back(cir.back());
			swap(node[cir.front()].to, node[cir.back()].to);
			cir.pop_front();
			cir.pop_back();
		}
	}
	
	//判断上一步是否有操作
	if (!ans1.empty()) {
		cout << 2 << endl;
		out();
	} else {
		cout << 1 << endl;
	}
	
	//将所有小环对调
	flag.reset();
	for (int i = 1; i <= n; ++i) {
		if (node[i].to == i) continue;
		if (flag[i]) continue;
		ans1.push_back(i);
		ans2.push_back(node[i].to);
		flag[i] = 1;
		flag[node[i].to] = 1;
	}
	out();
	
	return;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
//	int T; cin >> T; while (T--)
	Solve();
	return 0;
}