P7827 "RdOI R3 Additional" ACP-I

**Note: This is not a simulation problem. Please read the entire statement carefully before you start.** --- ### Leaderboard | task | Shortest Lines | Achiever | | ---- | -------------- | ------------- | | 1 | 5 | std | | 2 | 191 | \_\_Ultimium\_\_ | | 3 | 845 | dead_X | | 4 | 24 | 囧仙 (jiong xian) | | 5 | 77 | dqstz | | 6 | 15078 | 寻逍遥2006 (xun xiao yao 2006) | | 7 | 211 | liqingyang | | 8 | 6796 | liqingyang | If your solution uses **strictly fewer** lines than the number on the list, please contact @[yzy1](/user/207996) to add your result to the leaderboard. --- The problem name ACP has two meanings: **A**ncient **C**omputer **P**rogram and **A**nother **C**onstruct **P**roblem. In 1951, on the eve of the $-32$-th National Olympiad in Informatics winter camp for teenagers, Little A used a Time Transport Interface (**T**ime **T**ransport **I**nterface) 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.

**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. | Name | Parameters | Description | Pseudocode | | -------------------- | ------------------------- | --------------------------------------------------------------- | -------------------------------------------------------------- | | $\textbf{and}\ i$ | $i \in [0,1]$ | Set $T_i$ to the bitwise AND of $T_i$ and the other stack’s top. | $T_i \gets T_i \operatorname{\And} T_{i \oplus 1}$ | | $\textbf{or}\ i$ | $i \in [0,1]$ | Set $T_i$ to the bitwise OR of $T_i$ and the other stack’s top. | $T_i \gets T_i \mid T_{i \oplus 1}$ | | $\textbf{xor}\ i$ | $i \in [0,1]$ | Set $T_i$ to the bitwise XOR of $T_i$ and the other stack’s top. | $T_i \gets T_i \oplus T_{i \oplus 1}$ | | $\textbf{lsh}\ i\ j$ | $i \in [0,1],j\in[0,64]$ | Set $T_i$ to $T_i$ left-shifted by $j$ bits, with natural overflow. | $T_i \gets T_i \times 2^j \bmod 2^{64}$ | | $\textbf{rsh}\ i\ j$ | $i \in [0,1],j\in[0,64]$ | Set $T_i$ to $T_i$ right-shifted by $j$ bits, with natural overflow. | $T_i \gets \lfloor \dfrac{T_i}{2^j} \rfloor$ | | $\textbf{not}\ i$ | $i\in[0,1]$ | Set $T_i$ to the bitwise NOT of $T_i$. | $T_i \gets (2^{64}-1)-T_i$ | | $\textbf{pop}\ i$ | $i\in[0,1]$ | Pop the top element of stack $S_i$. | $\text{Remove top element of }S_i$ | | $\textbf{mov}\ i$ | $i\in[0,1]$ | Move $T_i$ from $S_i$ to the other stack, i.e., to $S_{i \oplus 1}$. | $\text{Push}\ T_i\text{ to }S_{i\oplus 1};\ \textbf{pop}\ i$ | 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. 1. Input $a,b$, output $(a-b+2^{64}) \bmod 2^{64}$. That is, compute the difference with natural overflow. 1. 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. 1. Input $a$, output $(\operatorname{popcnt}a) \bmod 2$. Here $\operatorname{popcnt} x$ is the number of $1$ bits in the binary representation of $x$. 1. Input $a,b$, output $\min\{a,b\}$. 1. 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$. 1. Input $a$, where both $a$ and the answer are non-negative powers of $2$ or zero, output $\sqrt a$. 1. Input $a,b;1\le a,b \le 63$, output $\gcd(a,b)$, i.e., the greatest common divisor of $a,b$.

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.**

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

### 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