解题思路

题目要求我们找到一个长度为 $n$ 的排列 $A$，使得序列 $\{|A_i - i|\}$ 恰好是 $0$ 到 $n-1$ 的一个排列。这种排列被称为完美排列。

关键观察

1. 存在条件：经过分析可以发现，完美排列存在的充分必要条件是 $n$ 满足 $n \equiv 0 \pmod{4}$ 或 $n \equiv 1 \pmod{4}$。换句话说，当 $n$ 除以 4 余 0 或 1 时，存在完美排列；否则不存在（输出 0）。
2. 构造方法：
   • 当 $n = 4k$ 时：
     • 排列的构造方式是分段构造，具体如下：
       • 第一个数是 $2k+1$。
       • 接着是 $4k$ 到 $3k+2$ 的递减序列。
       • 然后是 $3k$ 到 $2k+2$ 的递减序列。
       • 接着是 $2k$ 到 $k+1$ 的递减序列。
       • 然后是 $3k+1$。
       • 最后是 $k$ 到 $1$ 的递减序列。
   • 当 $n = 4k + 1$ 时：
     • 排列的构造方式类似于 $n=4k$，但需要额外处理最后一个数：
       • 第一个数是 $4k+1$。
       • 接着是 $4k$ 到 $3k+2$ 的递减序列。
       • 然后是 $3k$ 到 $2k+2$ 的递减序列。
       • 接着是 $2k$ 到 $k+1$ 的递减序列。
       • 如果 $k \neq 0$，输出 $3k+1$。
       • 然后是 $k$ 到 $1$ 的递减序列。
       • 如果 $k \neq 0$，最后输出 $2k+1$。
3. 其他情况：如果 $n$ 不满足 $n \equiv 0 \pmod{4}$ 或 $n \equiv 1 \pmod{4}$，则直接输出 0。

#include<cstdlib>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int main()
{
	int N,k;
	while(scanf("%d",&N)==1)
	{
		if(N%4==0)
		{
			k=N/4;
			printf("%d ",2*k+1);
			for(int i=4*k;i>=3*k+2;i--)printf("%d ",i);
			for(int i=3*k;i>=2*k+2;i--)printf("%d ",i);
			for(int i=2*k;i>=k+1;i--)printf("%d ",i);
			printf("%d ",3*k+1);
			for(int i=k;i>=1;i--)printf("%d ",i);
		}
		else if(N%4==1)
		{
			k=(N-1)/4;
			printf("%d ",4*k+1);
			for(int i=4*k;i>=3*k+2;i--)printf("%d ",i);
			for(int i=3*k;i>=2*k+2;i--)printf("%d ",i);
			for(int i=2*k;i>=k+1;i--)printf("%d ",i);
			if(k)printf("%d ",3*k+1);
			for(int i=k;i>=1;i--)printf("%d ",i);
			if(k)printf("%d ",2*k+1);
		}
		else
		{
			printf("0");
		}
		putchar('\n');
	}
	return 0;
}