Background

Note: This is not a simulation problem. Please read the entire statement carefully before you start.

Leaderboard

If your solution uses strictly fewer lines than the number on the list, please contact

The problem name ACP has two meanings: Ancient Computer Program and Another Construct Problem.

In 1951, on the eve of the $-32$-th National Olympiad in Informatics winter camp for teenagers, Little A used a Time Transport Interface (Time Transport Interface) to connect to a computer from 2015, and obtained the problems of the 32nd winter camp to practice.

He opened the third problem, "Future Program":

This is an output-only problem with 10 test points.
For each test point, you are given the source code of a program and the input of that program. You need to run the program and save its output.
Unfortunately, these programs are extremely inefficient, and cannot produce output within the 5-hour contest time.

Little A thought about it and decided to try running this problem on a 1951 computer. However, because the 1951 computer has too little storage space, he cannot transfer the attachments and data. Please help Little A write the standard solution to generate testdata.

Problem Description

This is an output-only problem.

Little A's antique computer uses two stacks of $64$-bit unsigned integers, $S_0$ and $S_1$, to store data. Each stack initially contains $10^{10^{10}}$ zeros.

For convenience, let "$T_x$" denote the top element of stack $S_x$. Let the symbols "$\And$", "$\mid$", and "$\oplus$" represent bitwise AND, bitwise OR, and bitwise XOR operations, respectively.

This computer supports 8 assembly instructions. Unless otherwise stated, all parameters of the following instructions are integers.

You need to use these assembly instructions to implement several computation tasks, where each test point corresponds to a separate task.

Below, "input $a_1, a_2, \cdots$" means pushing the integers $a_1,a_2,\cdots$ into stack $S_0$ in order, while the zeros at the bottoms of both stacks remain unchanged. Unless otherwise stated, all input numbers are integers in the range $\mathbf{[0,2^{64}-1]}$.
"Output $x_1, x_2, \cdots$" means that after the instructions finish running, several integers will be taken out from $S_1$ in order as $x_1,x_2,\cdots$ to check whether the result is correct. Besides these, after execution, all numbers in $S_0$ and all numbers in $S_1$ that are not taken out may be arbitrary.

1. Input $a, b$, output $b,a$. That is, swap the two numbers.
2. Input $a,b$, output $(a-b+2^{64}) \bmod 2^{64}$. That is, compute the difference with natural overflow.
3. Input $a_1, a_2,\cdots,a_9; a_i\in[48,57]$, i.e. $a_i\in[\mathtt{'0'}, \mathtt{'9'}]$. Treat $a_1\sim a_9$ as a length-$9$ string under ASCII encoding. You need to reverse the string and then convert it into the corresponding decimal integer and output it. That is, implement a fast input routine. In particular, the string may have leading zeros.
4. Input $a$, output $(\operatorname{popcnt}a) \bmod 2$. Here $\operatorname{popcnt} x$ is the number of $1$ bits in the binary representation of $x$.
5. Input $a,b$, output $\min\{a,b\}$.
6. Input $a,b,p$, where $p$ is a non-negative power of $2$ or zero. Output $(a\times b) \bmod p$. In particular, when $p=0$, output $0$.
7. Input $a$, where both $a$ and the answer are non-negative powers of $2$ or zero, output $\sqrt a$.
8. Input $a,b;1\le a,b \le 63$, output $\gcd(a,b)$, i.e., the greatest common divisor of $a,b$.

Input Format

Since the setter does not want to make this a big simulation problem, the assembly simulation part is provided in the attachment.

In the distributed files, there are checker.cpp and 1.ans ~ 8.ans. Among them, checker.cpp provides simple implementations of several assembly instructions. You can use checker.cpp to test your program. Compile checker.cpp with g++ checker.cpp -o checker -std=c++11 into an executable, then run checker *.in *.out *.ans. The checker will output your results and the score for that test point. Here *.in contains the input data given to the instructions, one per line, ending at EOF; *.out stores your instructions; *.ans refers to the .ans files in the distributed package.

Note: This checker is only a sample and does not have the ability to verify correctness.

Output Format

Please write the instructions for each task into 1.out ~ 8.out, then pack them into a zip and submit.

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

Hint

Sample Explanation

The above "sample groups $1\sim 8$" represent the sample input/output for subtasks $1\sim8$. "Sample groups $9\sim10$" are one shortest program implementation for an example problem.

Scoring

Let * denote the test point index. If your instructions (*.out) do not correctly complete the computation, you get $0$ points. Otherwise, let the number of instructions you used be $cnt$. If there are $x$ numbers in *.ans that satisfy $\ge cnt$, then you get $x$ points for that test point.

Notes

Although you are allowed to submit up to $999999$ lines of instructions, due to Luogu’s time limit for running the checker, your instruction length is forced to have a strange upper bound: approximately $2\times 10^5$. If you exceed this length, the checker may time out and cause UKE.

Due to the nature of Luogu output-only problems, if you cannot solve some tasks, please put an empty *.out file as a placeholder in the zip, where * is the task number. Otherwise, the whole problem may have mismatched answers (for example, 2.out being submitted to test point $1$), causing the following test points to become $0$ points.

Translated by ChatGPT 5