P8523 [IOI 2021] Shift Register

**Abusing the judging system for this problem will result in an account ban.** **Due to technical limitations, please do not submit this problem using C++ 14 (GCC 9).** This is an interactive problem. You only need to implement the function required in the code. Your code does not need to include any extra header files, and you do not need to implement the `main` function. At the beginning of your code, you need to add the following code: ```cpp #include void append_move(int t, int y); void append_store(int t, std::vector v); void append_and(int t, int x, int y); void append_or(int t, int x, int y); void append_xor(int t, int x, int y); void append_not(int t, int x); void append_left(int t, int x, int p); void append_right(int t, int x, int p); void append_add(int t, int x, int y); void append_print(int t); ```

Engineer Christopher is developing a new computer processor. This processor can access $m$ different $b$-bit storage units (in this problem, $m = 100$ and $b = 2000$). They are called registers, indexed from $0$ to $m - 1$. We denote these registers as $r[0], r[1], \ldots , r[m - 1]$. Each register is an array of $b$ bits, indexed from $0$ (the rightmost bit) to $b - 1$ (the leftmost bit). For all $i$ ($0 \le i \le m - 1$) and $j$ ($0 \le j \le b - 1$), we denote the $j$-th bit of register $i$ as $r[i][j]$. For any bit sequence $d_0, d_1, \ldots , d_{l - 1}$ (of some length $l$), its integer value is $2^0 \cdot d_0 + 2^1 \cdot d_1 + \cdots + 2^{l - 1} \cdot d_{l - 1}$. We say the integer stored in a register is the integer value of the bit sequence in the register, i.e., it is $2^0 \cdot r[i][0] + 2^1 \cdot r[i][1] + \cdots + 2^{b - 1} \cdot r[i][b - 1]$. The processor has $9$ types of instructions that can be used to modify the bits in registers. Each instruction operates on one or more registers and stores its output into one of the registers. Below, we use $x := y$ to denote an operation that changes the value of $x$ to become $y$. The operations of each instruction type are described as follows. $\operatorname{\mathit{move}}(t, y)$: Copy the bit array in register $y$ to register $t$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := r[y][j]$. $\operatorname{\mathit{store}}(t, v)$: Set register $t$ to $v$, where $v$ is a $b$-bit array. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := v[j]$. $\operatorname{\mathit{and}}(t, x, y)$: Compute the bitwise AND of registers $x$ and $y$, and store the result in register $t$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := 1$ if both $r[x][j]$ and $r[y][j]$ are $1$, otherwise set $r[t][j] := 0$. $\operatorname{\mathit{or}}(t, x, y)$: Compute the bitwise OR of registers $x$ and $y$, and store the result in register $t$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := 1$ if at least one of $r[x][j]$ and $r[y][j]$ is $1$, otherwise set $r[t][j] := 0$. $\operatorname{\mathit{xor}}(t, x, y)$: Compute the bitwise XOR of registers $x$ and $y$, and store the result in register $t$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := 1$ if exactly one of $r[x][j]$ and $r[y][j]$ is $1$, otherwise set $r[t][j] := 0$. $\operatorname{\mathit{not}}(t, x)$: Compute the bitwise NOT of register $x$, and store the result in register $t$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := 1 - r[x][j]$. $\operatorname{\mathit{left}}(t, x, p)$: Shift all bits in register $x$ left by $p$ positions, and store the result in register $t$. The result of shifting register $x$ left by $p$ is a $b$-bit array $v$. For all $j$ ($0 \le j \le b - 1$), if $j \ge p$ then $v[j] = r[x][j - p]$, otherwise $v[j] = 0$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := v[j]$. $\operatorname{\mathit{right}}(t, x, p)$: Shift all bits in register $x$ right by $p$ positions, and store the result in register $t$. The result of shifting register $x$ right by $p$ is a $b$-bit array $v$. For all $j$ ($0 \le j \le b - 1$), if $j \le b - 1 - p$ then $v[j] = r[x][j + p]$, otherwise $v[j] = 0$. For all $j$ ($0 \le j \le b - 1$), set $r[t][j] := v[j]$. $\operatorname{\mathit{add}}(t, x, y)$: Add the integer values in registers $x$ and $y$, and store the result in register $t$. The addition is done modulo $2^b$. More formally, let $X$ be the integer value in register $x$ before the operation, and $Y$ be the integer value in register $y$ before the operation. Let $T$ be the integer value in register $t$ after the operation. If $X + Y < 2^b$, set the bits in $t$ so that $T = X + Y$. Otherwise, set the bits in $t$ so that $T = X + Y - 2^b$. Christopher wants you to solve two tasks using this new processor. The task type is given by an integer $s$. For all task types, you need to create a program that is a sequence of the instructions defined above. The program input consists of $n$ integers $a[0], a[1], \ldots , a[n - 1]$, and each integer has $k$ bits, i.e., $a[i] < 2^k$ ($0 \le i \le n - 1$). Before the program is executed, all input numbers are stored in register $0$ in order, so that for all $i$ ($0 \le i \le n - 1$), the integer value of the $k$-bit sequence $r[0][i \cdot k], r[0][i \cdot k + 1], \ldots , r[0][(i + 1) \cdot k - 1]$ equals $a[i]$. Note that $n \cdot k \le b$. All other bits in register $0$ (with indices between $n \cdot k$ and $b - 1$, inclusive), as well as all bits in all other registers, are initialized to $0$. Executing a program means executing its instructions in order. After the last instruction is executed, the program output is computed from the final values of the bits in register $0$. Specifically, the output is a sequence of $n$ integers $c[0], c[1], \ldots , c[n - 1]$, where for each $i$ ($0 \le i \le n - 1$), $c[i]$ is the integer value of the sequence of bits in register $0$ from $i \cdot k$ to $(i + 1) \cdot k - 1$. Note that after the program finishes, the remaining bits in register $0$ (with indices at least $n \cdot k$), as well as all bits in other registers, may have arbitrary values. The first task ($s = 0$) is to find the minimum among the input integers $a[0], a[1], \ldots , a[n - 1]$. Specifically, $c[0]$ must be the minimum of $a[0], a[1], \ldots , a[n - 1]$. The values of $c[1], c[2], \ldots , c[n - 1]$ can be arbitrary. The second task ($s = 1$) is to sort the input integers $a[0], a[1], \ldots , a[n - 1]$ in non-decreasing order. Specifically, for all $i$ ($0 \le i \le n - 1$), $c[i]$ should equal the $(1 + i)$-th smallest integer among $a[0], a[1], \ldots , a[n - 1]$ (that is, $c[0]$ is the smallest input integer). Please help Christopher write programs to solve these tasks. Each program may contain at most $q$ instructions.

You need to implement the following function: ```cpp void construct_instructions(int s, int n, int k, int q) ``` - $s$: the task type. - $n$: the number of integers in the input. - $k$: the number of bits in each input integer. - $q$: the maximum allowed number of instructions. This function will be called exactly once, and it should create a sequence of instructions for the required task. This function should call one or more of the following functions to create the instruction sequence: ```cpp void append_move(int t, int y) void append_store(int t, std::vector v) void append_and(int t, int x, int y) void append_or(int t, int x, int y) void append_xor(int t, int x, int y) void append_not(int t, int x) void append_left(int t, int x, int p) void append_right(int t, int x, int p) void append_add(int t, int x, int y) ``` - Each function appends one instruction $\operatorname{\mathit{move}}(t, y)$, $\operatorname{\mathit{store}}(t, v)$, $\operatorname{\mathit{and}}(t, x, y)$, $\operatorname{\mathit{or}}(t, x, y)$, $\operatorname{\mathit{xor}}(t, x, y)$, $\operatorname{\mathit{not}}(t, x)$, $\operatorname{\mathit{left}}(t, x, p)$, $\operatorname{\mathit{right}}(t, x, p)$, or $\operatorname{\mathit{add}}(t, x, y)$, respectively. - For all relevant instructions, $t$, $x$, and $y$ must be at least $0$ and at most $m - 1$. - For all relevant instructions, $t$, $x$, and $y$ do not have to be pairwise distinct. - For the `left` and `right` instructions, $p$ must be at least $0$ and at most $b$. - For the `store` instruction, the length of $v$ must be $b$. You may also call the following function to help test your solution: ```cpp void append_print(int t) ``` - When judging your solution, all calls to this function will be ignored. - In the sample evaluator, this function appends a $\operatorname{\mathit{print}}(t)$ operation to the program. - When the sample evaluator executes a program and encounters a $\operatorname{\mathit{print}}(t)$ operation, it prints the $n$ $k$-bit integers formed by the first $n \cdot k$ bits of register $t$. - $t$ must satisfy $0 \le t \le m - 1$. - Any call to this function will not be counted in the number of instructions you create. After appending the last instruction, `construct_instructions` should return. Then, the program you created will be judged on a number of test cases, where each test case provides input data consisting of $n$ $k$-bit integers $a[0], a[1], \ldots , a[n - 1]$. If the output $c[0], c[1], \ldots , c[n - 1]$ produced by your program for the given input data satisfies the following conditions, your solution will be considered accepted for that test case: - If $s = 0$, $c[0]$ should be the minimum of $a[0], a[1], \ldots , a[n - 1]$. - If $s = 1$, for all $i$ ($0 \le i \le n - 1$), $c[i]$ should be the $(1 + i)$-th smallest integer among $a[0], a[1], \ldots , a[n - 1]$. When judging your solution, one of the following error messages may be given: - `Invalid index`: the register index given as $t$, $x$, or $y$ in some function call is invalid (possibly negative). - `Value to store is not b bits long`: the length of $v$ provided to `append_store` is not equal to $b$. - `Invalid shift value`: the value of $p$ provided to `append_left` or `append_right` is not between $0$ and $b$ (inclusive). - `Too many instructions`: your function attempts to append more than $q$ instructions.

N/A

For all testdata: - $m = 100$. - $b = 2000$. - $0 \le s \le 1$. - $2 \le n \le 100$. - $1 \le k \le 10$. - $q \le 4000$. - $0 \le a[i] \le 2^k - 1$ (for all $0 \le i \le n - 1$). Subtasks | Score | Special constraints :-:|:-:|:-: $1$ | $10$ | $s = 0$, $n = 2$, $k \le 2$, $q = 1000$. $2$ | $11$ | $s = 0$, $n = 2$, $k \le 2$, $q = 20$. $3$ | $12$ | $s = 0$, $q = 4000$. $4$ | $25$ | $s = 0$, $q = 150$. $5$ | $13$ | $s = 1$, $n \le 10$, $q = 4000$. $6$ | $29$ | $s = 1$, $q = 4000$. Thanks to @[Bingxiu](https://www.luogu.com.cn/user/676498) for providing the interactive library. The interactive library in the attachment can be used for local testing, and it is different from the interactive library used in the actual judging. Translated by ChatGPT 5