「RdOI R3 附加」ACP-I

**注意：这不是一道模拟题，请先完整地读完一遍题面后再开始做题。** --- ### 排行榜 | task | 最短行数 | 达成者 | | ---- | -------- | ----------- | | 1 | 5 | std | | 2 | 191 | \_\_Ultimium\_\_ | | 3 | 845 | dead_X | | 4 | 24 | 囧仙 | | 5 | 77 | dqstz | | 6 | 15078 | 寻逍遥2006 | | 7 | 211 | liqingyang | | 8 | 6796 | liqingyang | 如有你的解法行数**严格小于**榜中行数，请联系 @[yzy1](/user/207996) 把你的成绩放到排行榜上。 --- 题目 ACP 有两层意思：**A**ncient **C**omputer **P**rogram 和 **A**nother **C**onstruct **P**roblem。 在 1951 年，第 -32 届全国青少年信息学奥林匹克冬令营前夕，小 A 借助时空传输接口（**T**ime **T**ransport **I**nterface）连接了一台 2015 年的计算机，获取到了第 32 届冬令营的题目来练习。 他打开了第三题「未来程序」这道题目： > 本题是一道提交答案题，一共 10 个测试点。 > 对于每个测试点，你会得到一段程序的源代码和这段程序的输入。你要运行这个程序，并保存这个程序的输出。 > 遗憾的是这些程序都效率极其低下，无法在比赛的 5 个小时内得到输出。 小 A 想了一下，决定用 1951 年的计算机来试着运行这个题目。但是因为 1951 年的电脑存储空间过小，导致他无法传输题目附件和数据，请你帮助小 A 写 std 造数据。

**这是一道提交答案题。** 小 A 的古董计算机使用两个 $64$ 位无符号整数的栈 $S_0$ 和 $S_1$ 来存储数据。每个栈中初始存储着 $10^{10^{10}}$ 个 $0$。 为了表述方便，下文中记「$T_x$」表示栈 $S_x$ 的栈顶元素。记符号 「$\And$」「$\mid$」「$\oplus$」分别为按位与、按位或、按位异或运算。 这台计算机支持 $8$ 种汇编指令，若没有特殊说明，以下指令的参数均为整数。 | 名称 | 参数 | 说明 | 伪代码 | | -------------------- | ------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ | | $\textbf{and}\ i$ | $i \in [0,1]$ | 令 $T_i$ 为 $T_i$ 与另一个栈的栈顶数字按位与的结果。 | $T_i \gets T_i \operatorname{\And} T_{i \oplus 1}$ | | $\textbf{or}\ i$ | $i \in [0,1]$ | 令 $T_i$ 为 $T_i$ 与另一个栈的栈顶数字按位或的结果。 | $T_i \gets T_i \mid T_{i \oplus 1}$ | | $\textbf{xor}\ i$ | $i \in [0,1]$ | 令 $T_i$ 为 $T_i$ 与另一个栈的栈顶数字按位异或的结果。 | $T_i \gets T_i \oplus T_{i \oplus 1}$ | | $\textbf{lsh}\ i\ j$ | $i \in [0,1],j\in[0,64]$ | 令 $T_i$ 为 $T_i$ 左移 $j$ 位的结果，自然溢出。 | $T_i \gets T_i \times 2^j \bmod 2^{64}$ | | $\textbf{rsh}\ i\ j$ | $i \in [0,1],j\in[0,64]$ | 令 $T_i$ 为 $T_i$ 右移 $j$ 位的结果，自然溢出。 | $T_i \gets \lfloor \dfrac{T_i}{2^j} \rfloor$ | | $\textbf{not}\ i$ | $i\in[0,1]$ | 令 $T_i$ 为 $T_i$ 按位取反的结果。 | $T_i \gets (2^{64}-1)-T_i$ | | $\textbf{pop}\ i$ | $i\in[0,1]$ | 将栈 $S_i$ 的栈顶元素出栈。 | $\text{Remove top element of }S_i$ | | $\textbf{mov}\ i$ | $i\in[0,1]$ | 将 $T_i$ 出 $S_i$ 栈，然后将其入另一个栈。即移动 $T_i$ 至 $S_{i \oplus 1}$。 | $\text{Push}\ T_i\text{ to }S_{i\oplus 1};\ \textbf{pop}\ i$ | 你需要使用这些汇编指令实现若干计算任务，每个测试点对应一个单独的计算任务。下文中「输入 $a_1, a_2, \cdots$」表示将 $a_1,a_2,\cdots$ 这几个整数**依次**压入 $S_0$ 栈，而两栈栈底的 $0$ 不做变动。**若无特殊说明，输入的数均为 $\mathbf{[0,2^{64}-1]}$ 范围内的整数。**「输出 $x_1, x_2, \cdots$」表示指令运行结束后会从 $S_1$ 中**依次**取出若干个整数作为 $x_1,x_2,\cdots$ 来检验结果是否正确。除此之外，对于 $S_0$ 栈中所有的数和 $S_1$ 栈中**没有**被取出的数在指令运行结束后可以为任意值。 1. 输入 $a, b$，输出 $b,a$。即将两数交换。 1. 输入 $a,b$，输出 $(a-b+2^{64}) \bmod 2^{64}$。即求两数之差，自然溢出。 1. 输入 $a_1, a_2,\cdots,a_9;a_i\in[48,57]$，即 $a_i\in[\mathtt{'0'}, \mathtt{'9'}]$。将 $a_1\sim a_9$ 视为一个 ASCII 编码下的长度为 $9$ 的字符串，你需要将这个字符串**前后翻转后**转化为一个对应的十进制整数并输出。即实现一个快读。特别的，字符串中可能会有前导零。 1. 输入 $a$，输出 $(\operatorname{popcnt}a) \bmod 2$。其中 $\operatorname{popcnt} x$ 代表 $x$ 的二进制表示法中 $1$ 的个数。 1. 输入 $a,b$，输出 $\min\{a,b\}$。 1. 输入 $a,b,p$，满足 $p$ 为 $2$ 的非负整数次幂或零。输出 $(a\times b) \bmod p$。特别地，当 $p=0$ 时输出 $0$。 1. 输入 $a$，满足 $a$ 和答案都是 $2$ 的非负整数次幂或零，输出 $\sqrt a$。 1. 输入 $a,b;1\le a,b \le 63$，输出 $\gcd(a,b)$，即 $a,b$ 的最大公因数。

由于出题人不想把这道题出成一道大模拟，所以附件中提供了汇编模拟部分。 在下发文件下有 `checker.cpp` 和 `1.ans ~ 8.ans`。其中 `checker.cpp` 给出了几种汇编指令的简单实现。你可以使用 `checker.cpp` 测试你的程序。使用 `g++ checker.cpp -o checker -std=c++11` 将 `checker.cpp` 编译为可执行文件后运行 `checker *.in *.out *.ans`，`checker` 就会给出你的输出结果和该测试点的得分。其中 `*.in` 中为提供给指令的输入数据，每行一个，以 EOF 结束；`*.out` 中存放你的指令；`*.ans` 指下发文件中的 `.ans` 文件。 **注意：此 checker 仅作示例使用，不具备验证正确性功能。**

请将每个任务对应的指令写入 `1.out ~ 8.out`，并打包成 zip 后提交。

123456789
2147483648

2147483648
123456789

2147483647998244353
9982443532147483647

10611784189560312322

51
53
51
52
52
50
56
57
57

998244353

233456

1

2147483647998244353
9223372036854775808

2147483647998244353

2147483647998244353
9982443532147483647
9223372036854775808

7806477557104029183

4611686018427387904

2147483648

24 32

8

输入 a，b。输出 a 按位异或 b 的结果。

mov 0
xor 1

没有输入，输出数字 6。

not 1
lsh 1 62
rsh 1 61

### 样例说明 上述「样例组 $1\sim 8$」代表 $1\sim8$ 子任务的样例输入输出。「样例组 $9\sim10$」为示例问题的一种最短的程序实现。 --- ### 评分方法 下面用 `*` 代表测试点编号。如果你提交的指令（`*.out`）没有正确完成计算得零分，否则设你使用的指令个数为 $cnt$，若 `*.ans` 中有 $x$ 个 $\ge cnt$ 的数，你该测试点得 $x$ 分。 --- ### 注意 虽然我们允许你提交最多 $999999$ 行的指令，但是由于洛谷对于 checker 的运行时间有限制，你的指令长度被强行加上了一个奇怪的上限：约是 $2\times 10^5$，超过这个长度的指令可能会因为 checker 超时而导致 UKE。 由于洛谷提交答案题的特性，如果你不会做一些 task，请在压缩包内放一个空的 `*.out` 文件占位，其中 `*` 代表 task 编号。否则你的整道题可能会出现答案错位（比如 `2.out` 交到了 $1$ 号测试点）的情况，导致后面的测试点变成零分。