[COI 2021] MalnaRISC

ID: 7470

远端评测题

1000ms

512MiB

难度: 6

上传者:

标签>

2021

Special Judge

COCI

题目描述

译自 COI 2021 T4「MalnaRISC」

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

MalnaRISC 仅支持一种命令 CMPSWP $R_i$ $R_j$ ，其含义为，比较 $R_i$ 与 $R_j$ 的大小，若 $R_i>R_j$ ，交换他们。

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

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

仅一行一个整数 $N$ 。

第一行为一个整数 $t$ ，表示您的代码长度。

接下来 $t$ 行，每行表示您的一行代码。

1
CMPSWP R1 R2

3
CMPSWP R1 R2
CMPSWP R1 R3
CMPSWP R2 R3

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

Subtask	$N$	$t_1$	$t_2$	$t_3$	分数
$1$	$8$	$28$	$12$	$6$	$10$
$2$	$13$	$78$	$22$	$10$	$10$
$3$	$16$	$120$	$28$	$10$	$10$
$4$	$32$	$496$	$60$	$15$	$10$
$5$	$53$	$1378$	$102$	$21$	$10$
$6$	$64$	$2016$	$124$	$21$	$10$
$7$	$73$	$2628$	$142$	$28$	$10$
$8$	$82$	$3321$	$160$	$28$	$10$
$9$	$91$	$4095$	$178$	$29$	$10$
$10$	$100$	$4950$	$196$	$30$	$10$

如果您的正确代码是 $t$ 行，那么您将获得这个分数四舍五入后的结果：

\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}