UOJ Logo Universal Online Judge

UOJ

#594. 新年的挑战

统计

本题是一道传统题,你需要编写程序输出题目规定的 hei++ 代码,而非直接提交 hei++ 代码。

你最后来到了黑衣人 $05$ 的老巢,神牪犇已经被他吃进了肚子里。

你伪装成他的手下,没想到的是黑衣人 $05$ 转手就丢给你好多任务,你不得不去完成来获得他的信任。

你要在一台奇怪的计算机上完成任务(称之为嘿嘿计算机)。这台计算机最小的存储单位为 $32$ 位的有符号整数(即 int,存储范围为 $\left[-2^{31},2^{31}\right)$ 中的整数);内存包含 $N=10^8$ 个存储单元,还有大小为 $32$ 个单元的寄存器(一种速度较快的存储单元)。我们用 $s[0],s[1],\dots,s[N-1]$ 表示内存中的存储单元,$s[-1],s[-2],\dots,s[-32]$ 表示寄存器。计算机启动时,所有存储单元都被 $0$ 填充。

黑衣人要求你设计相应的程序,解决以下 $3$ 个任务。

任务一:排序

有 $n = 10^4$ 个 $\left[-2^{31}, 2^{31}\right)$ 内且互不相等的整数,存储在 $s[0],s[1],\dots,s[n-1]$,你需要将它们从小到大排序后存入 $s[0],s[1],\dots,s[n-1]$。

任务二:维护前缀和

你要维护一个大小为 $n = 10^4$ 的 $32$ 位有符号整型数组 $a[0],a[1],\ldots,a[n-1]$,初始值均为 $0$。

下面有 $n$ 次询问,第 $i$($0 \le i < n$)次询问的参数 $x[i],y[i],z[i]$,分别存储在 $s[n+3i]$, $s[n+3i+1]$, $s[n+3i+2]$,其中 $1 \le x[i] \le n$, $y[i] \in \left[-2^{31}, 2^{31}\right)$, $1 \le z[i] \le n$。

你需要先给 $a[x[i] - 1]$ 加上 $y$,再将 $\left[-2^{31},2^{31}\right)$ 中唯一的与 $a[0]+a[1]+\dots+a[z[i] - 1]$ 模 $2^{32}$ 同余的数存入 $s[n+3i+2]$。

保证 $x$ 构成一个 $1$ 到 $n$ 的排列。保证 $z$ 也构成一个 $1$ 到 $n$ 的排列。

注意:$s[0],s[1],\ldots,s[n-1]$ 这些位置是特地预留的,方便选手完成任务。

任务三:多项式乘法

有两个次数均不超过 $n = 2047$ 的多项式,其中 $s[0],s[1],\ldots,s[n]$ 存储着第一个多项式的 $0$ 到 $n$ 次项系数,$s[n+1],s[n+2],\ldots,s[2n+1]$ 中存储着第二个多项式的 $0$ 到 $n$ 次项系数。

你需要将这两个多项式相乘,得到一个次数不超过 $2n$ 的多项式,并将其 $0$ 到 $2n$ 次项系数对 $998244353$ 取模的结果存入 $s[0],s[1],\ldots,s[2n]$。

保证输入多项式的系数是 $[0,998244353)$ 内的整数。

技术细节

然而,嘿嘿计算机上并不能执行正常的程序,只能执行一种我们称之为 hei++ 的代码。

hei++ 代码包含若干行。每行可能的形式如下:

  1. ADD i j k:执行加法 $s[k] = s[i] + s[j]$(如果溢出了则结果为 $[-2^{31}, 2^{31})$ 中唯一的那个与 $s[i] + s[j]$ 模 $2^{32}$ 同余的数);
  2. SUB i j k:执行减法 $s[k] = s[i] - s[j]$(如果溢出了则结果为 $[-2^{31}, 2^{31})$ 中唯一的那个与 $s[i] - s[j]$ 模 $2^{32}$ 同余的数);
  3. ADDM i j m k:执行模意义下的加法,将 $s[k]$ 赋值为 $[0, s[m])$ 中唯一的那个与 $s[i] + s[j]$ 在模 $s[m]$ 意义下同余的数;
  4. SUBM i j m k:执行模意义下的减法,将 $s[k]$ 赋值为 $[0, s[m])$ 中唯一的那个与 $s[i] - s[j]$ 在模 $s[m]$ 意义下同余的数;
  5. CPY i k:执行赋值 $s[k] = s[i]$;
  6. SET x k:将 $s[k]$ 赋值为常量 $x \in \left[-2^{31}, 2^{31}\right)$;
  7. CMP i j k:若 $s[i] > s[j]$,将 $s[k]$ 赋值为 $1$,否则赋值为 $0$;
  8. JMP i l:表示若 $s[i] = 0$,则程序跳转到第 $l$ 行(行号从 $1$ 开始)的开头,否则无事发生;$l$ 需在 $1 \ldots \text{#lines} + 1$ 范围内,其中 $\text{#lines}$ 为你程序的总行数。当 $l=\text{#lines}+1$ 则会令程序立刻结束。
  9. ADV i k:执行赋值 $s[k] = s[s[i]]$;
  10. MUL i j m k:执行模意义下的乘法,将 $s[k]$ 赋值为 $[0, s[m])$ 中唯一的那个跟 $s[i] \times s[j]$ 在模 $s[m]$ 意义下同余的数(若 $s[m] \le 0$ 程序立刻崩溃);
  11. DIV i j k:将 $s[k]$ 赋值为 $s[i] / s[j]$ 向零舍入之后的结果(若 $s[j]=0$ 则程序立刻崩溃);
  12. COM i k:执行赋值 $s[s[k]] = s_i$。

除此之外,每行语句前面都可以加一个自定义的标签(但不能有两行拥有相同的标签),标签由大小写英文字母(大小写敏感)或数字组成,且必须以字母开头,例如:

  • hoho: ADD 2 3 3

然后在 hei++ 代码中,JMP 语句中的 $l$ 也可以设置为自定义的标签,例如:

  • JMP 3 hoho

你可以在 JMP 语句中令 l = exit 来达到满足条件就直接让程序退出的效果。

寄存器的写入速度比内存快很多,在操作 $1,2,3,4,5,6,7,9,10,11$ 中,如果被写入的目标 $s[k]$ 满足 $k < 0$,则指令消耗 $1$ 单位时间,否则消耗 $w$ 单位时间;在操作 $12$ 中,如果被写入的目标 $s[s[k]]$ 满足 $s[k] < 0$,则指令消耗 $1$ 单位时间,否则消耗 $w$ 单位时间;操作 $8$ 固定消耗 $1$ 单位时间。参数 $w$ 的值会在之后给出。

在上面的指令中,所有对 $s$ 的访问需满足下标在 $-32, -31, \ldots,0,\ldots, 10^8-1$ 范围内,同一指令涉及的不同下标可以相等。

每个任务都有时间上限,为 $T=2 \times 10^8$ 个单位时间。如果你违反了上面的语法规则,或整个程序的执行时间超过了 $T$,则你的程序计为 $0$ 分。

你的 hei++ 代码开始执行前,我们会将输入数据写入指定位置,其余位置均为 $0$;你的 hei++ 代码结束后我们会检查指定位置是否正确,其余位置的值我们并不关心。

注意:由于 hei++ 代码可能很长,我们要求你提交一个能输出 hei++ 代码的程序,而非 hei++ 代码本身。

输入格式

输入仅包含一个 $\{1,2,3\}$ 中的整数,表示任务编号。

输出格式

你的程序需根据任务编号输出一个符合上述说明的 hei++ 程序。

如何使用答案校验器

见答案校验器下载。你需要将 sim.cpptestlib.h 放在同一目录下,然后将 sim.cpp 编译成可执行文件 sim(注意开启 C++ 11 编译开关)。

sim 的用法为:

./sim <code-file> <task-id>

其中 <code-file> 为一个 hei++ 代码的文件名,task-id 为一个 $[0, 3]$ 之间的整数。

如果 task-id 介于 $[1, 3]$ 之间,则 sim 会按对应的任务进行测评。该答案校验器仅包含一组随机数据,比赛最终测试时会使用更多数据测评。

如果 task-id 等于 $0$ 则代表自定义测试。sim 会从标准输入读入 $w$, $n_i$, $n_o$。然后它会再读入 $n_i$ 个整数并按顺序放入 $s$ 的前 $n_i$ 个位置内,然后运行 hei++ 代码,结束后输出 $s$ 的前 $n_o$ 个位置。

限制与约定

下表中 $s$ 表示你的程序的运行时间,$u$ 是达到满分标准的最大时间。

任务编号 $w=$ $u=$ 评分方式
1 $114$ $10000000$ $40 \times \min(1,u/s)$
2 $32$ $2259485$ $30 \times \min(1,u/s)$
3 $16$ $3000000$ $s \le 6000000 \colon 30 \times \min(1,u/s)$,否则 $0$

时间限制:$\texttt{5s}$

内存限制:$\texttt{1GB}$

你的程序生成出来的代码大小不能超过 $64 \texttt{MB}$,行数不能超过 $2 \times 10^6$。

下载

样例答案校验器下载

后记

你趁获得黑衣人 $05$ 的信任后,趁其不备刺杀了他,并且把在黑衣人 $05$ 胃里的神牪犇救了出来。这时黑衣人 $05$ 的日记掉了出来,你了解到真正的幕后黑手,不是这些黑衣人——幕后黑手的真正名字,是五个黑衣人名字连起来得到的结果——然而,黑衣人 $05$ 的真实姓名,已经不得而知了……