#P8390. [COI2021] MalnaRISC

[COI2021] MalnaRISC

题目描述

译自 COI 2021 T4「MalnaRISC

您需要使用 MalnaRISC 这一神奇的处理器来解决知名问题——排序!

MalnaRISC 仅支持一种命令 CMPSWP RiR_i RjR_j,其含义为,比较 RiR_iRjR_j 的大小,若 Ri>RjR_i>R_j,交换他们。

MalnaRISC 最厉害的是,他可以同时运行多个不同的写在一行的程序,只要他们互不冲突,也就是说,CMPSWP 所接参数必须仅在同一行使用一次。

现在,请写一个处理长度为 NN 的序列的排序问题(按单调不降的顺序)的 MalnaRISC 程序,我们将根据您的程序长度进行评分。

输入格式

仅一行一个整数 NN

输出格式

第一行为一个整数 tt,表示您的代码长度。

接下来 tt 行,每行表示您的一行代码。

2
1
CMPSWP R1 R2

3
3
CMPSWP R1 R2
CMPSWP R1 R3
CMPSWP R2 R3

4
4
CMPSWP R1 R3
CMPSWP R2 R4
CMPSWP R1 R2 CMPSWP R3 R4
CMPSWP R2 R3

提示

Subtask NN t1t_1 t2t_2 t3t_3 分数
11 88 2828 1212 66 1010
22 1313 7878 2222 1010 1010
33 1616 120120 2828 1010
44 3232 496496 6060 1515 1010
55 5353 13781378 102102 2121 1010
66 6464 20162016 124124 1010
77 7373 26282628 142142 2828 1010
88 8282 33213321 160160 1010
99 9191 40954095 178178 2929 1010
1010 100100 49504950 196196 3030 1010

如果您的正确代码是 tt 行,那么您将获得这个分数四舍五入后的结果:

$$\text{score}(t)= \begin{cases} 0 & t>t_1\\ 1+\frac{2}{t-t_2} & t_1\ge t>t_2\\ 3+\frac{7(t_2-t+1)}{t_2-t_3} & t_2\ge t>t_3\\ 10 & t_3\ge t \end{cases} $$