UOJ Logo Universal Online Judge

UOJ

附件下载 统计

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

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

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

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

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

任务一:排序

n=104[231,231) 内且互不相等的整数,存储在 s[0],s[1],,s[n1],你需要将它们从小到大排序后存入 s[0],s[1],,s[n1]

任务二:维护前缀和

你要维护一个大小为 n=10432 位有符号整型数组 a[0],a[1],,a[n1],初始值均为 0

下面有 n 次询问,第 i0i<n)次询问的参数 x[i],y[i],z[i],分别存储在 s[n+3i], s[n+3i+1], s[n+3i+2],其中 1x[i]n, y[i][231,231), 1z[i]n

你需要先给 a[x[i]1] 加上 y,再将 [231,231) 中唯一的与 a[0]+a[1]++a[z[i]1]232 同余的数存入 s[n+3i+2]

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

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

任务三:多项式乘法

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

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

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

技术细节

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

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

  1. ADD i j k:执行加法 s[k]=s[i]+s[j](如果溢出了则结果为 [231,231) 中唯一的那个与 s[i]+s[j]232 同余的数);
  2. SUB i j k:执行减法 s[k]=s[i]s[j](如果溢出了则结果为 [231,231) 中唯一的那个与 s[i]s[j]232 同余的数);
  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[231,231)
  7. CMP i j k:若 s[i]>s[j],将 s[k] 赋值为 1,否则赋值为 0
  8. JMP i l:表示若 s[i]=0,则程序跳转到第 l 行(行号从 1 开始)的开头,否则无事发生;l 需在 1#lines+1 范围内,其中 #lines 为你程序的总行数。当 l=#lines+1 则会令程序立刻结束。
  9. ADV i k:执行赋值 s[k]=s[s[i]]
  10. MUL i j m k:执行模意义下的乘法,将 s[k] 赋值为 [0,s[m]) 中唯一的那个跟 s[i]×s[j] 在模 s[m] 意义下同余的数(若 s[m]0 程序立刻崩溃);
  11. DIV i j k:将 s[k] 赋值为 s[i]/s[j] 向零舍入之后的结果(若 s[j]=0 则程序立刻崩溃);
  12. COM i k:执行赋值 s[s[k]]=si

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

  • 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,,0,,1081 范围内,同一指令涉及的不同下标可以相等。

每个任务都有时间上限,为 T=2×108 个单位时间。如果你违反了上面的语法规则,或整个程序的执行时间超过了 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, ni, no。然后它会再读入 ni 个整数并按顺序放入 s 的前 ni 个位置内,然后运行 hei++ 代码,结束后输出 s 的前 no 个位置。

限制与约定

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

任务编号 w= u= 评分方式
1 114 10000000 40×min(1,u/s)
2 32 2259485 30×min(1,u/s)
3 16 3000000 s6000000:30×min(1,u/s),否则 0

时间限制:5s

内存限制:1GB

你的程序生成出来的代码大小不能超过 64MB,行数不能超过 2×106

下载

样例答案校验器下载

后记

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