P5207 [WC2019] Ancient Computer

Penguin Continent is a magical land. Beneath the thick ice lies a huge treasure. The explorer penguin Doudou dug through the ice and reached the treasury, but then he found a troubling problem. There are five vaults in total, and each vault is controlled by some ancient computers. Because they are so old, the programs inside these computers have already disappeared. Only by rewriting code for these computers, running it successfully, and producing the correct output can the door-opening mechanism be triggered.

Each vault gate is controlled by a computer cluster. The computers are connected by data cables to transmit data. However, many cables are broken, so only some connections remain. At the beginning, there is no data on any cable. When a computer writes to a cable, there will be an integer on that cable. Each cable can transmit at most one integer at the same time. After the integer is read, it disappears and the cable returns to the no-data state. Each ancient computer has two storage cells, named $a$ and $b$. Each cell can store an integer from $-2147483648$ to $2147483647$. At each moment, each ancient computer can execute one instruction. The instruction types are as follows: - `mov reg val`: set the value of storage cell `reg` to the value of `val`; - `add reg val`: add the value of `val` to storage cell `reg`; - `dec reg val`: subtract the value of `val` from storage cell `reg`; - `mul reg val`: multiply storage cell `reg` by the value of `val`; - `div reg val`: divide storage cell `reg` by the value of `val`; this division is truncation toward zero, e.g. $\frac{-5}{2} = -2$; - `and reg val`: bitwise AND storage cell `reg` with the value of `val`; - `or reg val`: bitwise OR storage cell `reg` with the value of `val`; - `xor reg val`: bitwise XOR storage cell `reg` with the value of `val`; - `jmp val`: jump to the `val`-th statement of the whole program. Statements are counted from the beginning of the program starting at $1$; - `jz reg val`: if the value of `reg` is $0$, jump to line `val`; - `jnz reg val`: if the value of `reg` is not $0$, jump to line `val`; - `jgz reg val`: if the value of `reg` is strictly greater than $0$, jump to line `val`; - `jsz reg val`: if the value of `reg` is strictly less than $0$, jump to line `val`; - `read x reg`: read a number from ancient computer $x$ into storage cell `reg`. If there is a cached number on the cable, read it and return; otherwise, wait and try again in the next cycle. When $x = 0$, it is considered reading one number from standard input; - `write val x`: write the value of `val` onto the cable in the direction of ancient computer $x$. This succeeds if and only if there is no data currently stored on the cable; otherwise, wait and try again in the next cycle. When $x = 0$, it is considered writing one number to standard output. `reg` denotes a storage cell, and can only be $a$ or $b$. `val` denotes the value of a storage cell or a number. For example, writing $a$ means the value stored in $a$, and writing $233$ means the number $233$. In the read/write instructions of an ancient computer, $x$ is considered a valid instruction only if $x$ is directly connected to the current ancient computer by a data cable, or $x = 0$. Each ancient computer has independent standard input and standard output. Different ancient computers do not affect each other. That is, each ancient computer has its own independent standard input port and standard output port. In each cycle, all ancient computers that need to execute `write` instructions are processed first, then those that need to execute `read` instructions, and finally those that need to execute other instructions. When reading, if there is no more data available from standard input, the ancient computer will enter an eternal waiting state. If an ancient computer finishes executing the last instruction, it will restart from the first instruction. If an ancient computer has no instructions at all, it will stay in an eternal waiting state. Instruction indices are positive integers starting from $1$. Each data cable can buffer at most one piece of data. Between two computers there is only one data cable, so it is possible to read the data written by itself in the previous round. If the two endpoint ancient computers read from or write to the same cable at the same time, the result will be unpredictable. There is no way to write to standard input, and there is no way to read from standard output. For example, the following sample reads two numbers from the standard input of computer $1$, and outputs the sum of the two numbers to the standard output of computer $2$. ```plain node 1 read 0 a read 0 b write a 2 write b 2 node 2 read 1 a read 1 b add a b write a 0 ``` The following is incorrect: ```plain node 1 read 0 a read 0 b add a b write a 0 node 2 mov a a ``` Because in the correct answer, the standard output of ancient computer $1$ is empty, while the standard output of ancient computer $2$ is the sum of the two numbers. #### Subtasks ##### Subtask 1 The standard input of ancient computer $1$ will contain no more than $100$ non-negative integers. Output them in the original order to the output of ancient computer $1$. ##### Subtask 2 Ancient computer $1$ will receive one non-negative integer $k$. Output the $k$-th term of the Fibonacci sequence to the standard output of node $1$ in the original input order. The input guarantees that the $k$-th term is at most $10^9$. The Fibonacci sequence is defined as $F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}(2 \le n)$. ##### Subtask 3 The standard input of ancient computer $1$ will contain no more than $100$ non-negative integers. Output them in the original order to the output of ancient computer $n$. ##### Subtask 4 Ancient computers $1$ to $50$ each input one number. Output these $50$ numbers from ancient computers $51$ to $100$. The output order is arbitrary, and each ancient computer may output any number of values. ##### Subtask 5 Ancient computers $1$ to $10$ each input one number. Output these numbers correspondingly from ancient computers $100$ to $91$. That is, the number input at node $i$ must be output from node $101 - i$.

This is an output-only problem. There are $5$ groups of input data, named `oldcomputer1.in` to `oldcomputer5.in`. These files describe the connection status between the ancient computers. The first line of the file contains three non-negative integers $x, n$ and $m$, representing the test point ID, the number of ancient computers, and the number of cables between them. The ancient computers are numbered from $1$ to $n$. The next $m$ lines each contain two positive integers $x, y$, indicating that computer $x$ and computer $y$ are directly connected by a data cable.

For each group of input data, you need to submit the corresponding output file `oldcomputer1.out` to `oldcomputer5.out`. These files describe the code content for each ancient computer. A file consists of multiple code blocks. The format of each code block is as follows: The first line contains a string `node` and an integer $a$ between $1$ and $n$, separated by a space, indicating that the following instructions belong to computer $a$. The following lines are the specific instructions of that computer. Each computer's instruction block should appear at most once; otherwise, unknown errors may occur. The total number of instruction lines for all computers must not exceed $10^6$.

#### Scoring For each test point, there are three parameters $a_1, a_2, a_3$. If the submitted code outputs the correct answer within $a_1$ cycles, you will get $100\%$ of the score for that test point. If the submitted code outputs the correct answer within $a_2$ cycles, you will get $60\%$ of the score for that test point. If the submitted code outputs the correct answer within $a_3$ cycles, you will get $30\%$ of the score for that test point. That is, at the end of each cycle, the answer will be checked once, and the earliest correct check result will be used. #### Subtask Scores | Subtask ID | $1$ | $2$ | $3$ | $4$ | $5$ | | :--------: | :--: | :--: | :--: | :--: | :--: | | CTT score | $10$ | $15$ | $15$ | $30$ | $30$ | | Non-CTT score | $20$ | $20$ | $20$ | $20$ | $20$ | #### Notes Thanks to @tiger2005 for providing the spj. For how to use the spj, please refer to these two discussion posts: - [Tester finished. ](https://www.luogu.com.cn/discuss/show/245001) - [Checker finished.](https://www.luogu.com.cn/discuss/show/245044). Translated by ChatGPT 5