「FAOI-R2」Program of atom(x) 2027 (D)
题目背景
这是来自 $2027$ 年的 FAOI 的一道题目,是一道带有 SPJ 的提交答案题,但也允许提交代码。
------------
自从 [krjt](https://www.luogu.com.cn/user/691537) 上次被 $160$ 人 [JC](https://www.luogu.com.cn/problem/T269289) 后,他换了一个「量子密码锁」,并用它锁上了自己的电脑包——打不开密码锁,就取不出包里的电脑。理论上,一旦 krjt 忘了密码,就连造这把锁的人也打不开。
然而,这把锁并非固若金汤。~~有一天,krjt 突然对化学产生了浓厚的兴趣。他拿起那把锁,放在酒精灯上加热,结果发现:~~ 在高温环境下,这把锁内的原子(严格来说是「离子」,下同)排布变得不稳定,这将导致它瘫痪。
题目描述
krjt 找来了密码锁的说明书:
> 在密码锁中,有一条长度为 $n$ 的链(不能更改,$n$ 的具体取值见密码锁铭牌),每个结点上可以存放至多一个原子。初始时,$1,2,\ldots,n$ 号原子以某个顺序(可以由用户自行调整)被存放在其中,每个结点存放一个原子。
>
> 定义 $i$ 号原子的电荷量为 $i!$。
>
> 现有一个计时器 $b$(单位为秒),其初值为 $0$。
>
> 密码锁被加热后,以下事件**依次循环发生**,直至达成停止条件:
>
> 1. 位于链两端的原子被移除(**这不会使链变短**),**不再对后续事件产生影响**;
> 2. 判定终止条件:
> - 若此时链中剩下不多于 $1$ 个原子(也可以是 $0$ 个),则**达成终止条件**,密码锁瘫痪(**此时计时器 $b$ 不会加 $1$**)。
> - 否则,将计时器 $b$ 的值加 $1$。
> 3. 给每个原子标定运动方向(**标定的运动方向是临时的,只生效一次,在下一次标定前会被重置**):
> - 计算它左边所有原子的电荷量之和为 $x$;
> - 计算它右边所有原子的电荷量之和为 $y$;
> - 如果 $x<y$,则标定方向为「向左」;
> - 如果 $x>y$,则标定方向为「向右」;
> - 可以证明,$x \ne y$。
> 4. 所有原子按照所标定的运动方向,移动一条边的距离,来到相邻的结点。
此外,krjt 从铭牌上读取到了 $n$ 的值。
krjt 定义,密码锁的瘫痪用时,为它瘫痪时 $b$ 的值。当然,krjt 希望密码锁尽量安全,因此他想**最大化密码锁的瘫痪用时**。
~~为了不让更多人再次 JC krjt~~,请问:他该如何排列密码锁中 $n$ 个原子的初始顺序?
输入输出格式
输入格式
一行一个正整数,$n$。
输出格式
一行 $n$ 个正整数,一个 $1 \sim n$ 的排列,表示你给 krjt 规划的排列方案:从左到右(或者从右到左,可以证明它们的瘫痪用时相等)依次输出 $n$ 个原子的编号。
**答案可能有多个,输出一个即可。**
**请注意:和许多其他的提交答案题不同的是,本题不下发数据文件(请自行输入 $n=1,2,\ldots,100$),并且你的答案必须是最优解才能 AC,否则不能得分。**
输入输出样例
输入样例 #1
1
输出样例 #1
1
输入样例 #2
2
输出样例 #2
1 2
输入样例 #3
3
输出样例 #3
2 1 3
输入样例 #4
4
输出样例 #4
4 2 3 1
输入样例 #5
5
输出样例 #5
5 4 1 2 3
输入样例 #6
6
输出样例 #6
2 4 5 1 6 3
说明
样例解释:
$6$ 个样例的瘫痪用时分别为 $0,0,0,1,1,2$ 秒。
实际上,枚举可知:当 $n \le 6$ 时,所有 $1 \sim n$ 的排列都是正确答案。
下面对样例 $6$ 进行模拟。在链的描述中:
- $0$ 表示该结点为空;
- $i$ 表示该结点上存放着 $i$ 号原子;
- $(x,y)$ 为计算结果。
1. **初始的链**为 $\color{blue}2-4-5-1-6-3$;
2. $b$ 初始为 $0$;
3. **位于两端的原子被移除**,链变为 $\color{blue}0-4-5-1-6-0$;
4. $b$ 增至 $1$;
5. **计算**,$4$ 个原子(从左向右)的结果分别为 $(\color{red}0\color{black},841),(\color{red}24\color{black},721),(\color{red}144\color{black},720),(145,\color{red}0\color{black})$;
6. 根据结果,左边 $3$ 个原子($4,5,1$)**向左运动**,最右边的原子($6$)**向右运动**,链变为 $\color{blue}4-5-1-0-0-6$;
7. **位于两端的原子被移除**,链变为 $\color{blue}0-5-1-0-0-0$;
8. $b$ 增至 $2$;
9. **计算**,$2$ 个原子(从左向右)的结果分别为 $(\color{red}0\color{black},1),(120,\color{red}0\color{black})$;
10. 根据结果,左边的原子($5$)**向左运动**,右边的原子($1$)**向右运动**,链变为 $\color{blue}5-0-0-1-0-0$;
11. **位于两端的原子被移除**,链变为 $\color{blue}0-0-0-1-0-0$;
11. 此时链中只剩下 $1$ 个原子($1$),**反应结束,密码锁瘫痪**。
综上,样例 $6$ 的瘫痪用时为 $2$ 秒。
------------
**本题允许提交答案。**
本题共 $100$ 个测试点,分别有 $n=1,2,\ldots,100$,每个 $1$ 分。
对于 $100\%$ 的数据,$1 \le n \le 100$。
> **提示 1:** 如果你 UKE 了,请联系出题人或管理员。
>
> **提示 2:** $n$ 的范围受到了洛谷的评测限制,否则它可以更大。
>
> **提示 3:** 提交答案时,$n$ 值应与测试点编号一致。
>
> **提示 4:** 本题可以当作传统题来做,提交答案只是为了方便打表。
>
> **提示 5:** 样例是手造的,不是 std 的运行结果。
>
> **提示 6:** 本题有 $6$ 分的样例分,一定要拿到哦!