P8523 [IOI 2021] 位移寄存器

**滥用本题评测将被封号** **由于技术限制，请不要使用 C++ 14 (GCC 9) 提交本题。** 这是一道交互题，你只需要实现代码中要求的函数。 你的代码不需要引用任何额外的头文件，也不需要实现 `main` 函数。 你的代码需要在开头添加以下代码： ```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); ```

工程师 Christopher 在开发一款新的计算机处理器。 这个处理器可以访问 $m$ 个不同的 $b$ 位存储单元（本题中 $m = 100$ 且 $b = 2000$）。它们被称作寄存器，编号从 $0 $ 到 $m - 1$。我们把这些寄存器记为 $r[0], r[1], \ldots , r[m - 1]$。每个寄存器都是 $b$ 个比特的数组，这些比特从 $0$（最右的比特）到 $b - 1$（最左的比特）编号。对所有的 $i$（$0 \le i \le m - 1$）和 $j$（$0 \le j \le b - 1$），我们将寄存器 $i$ 的第 $j$ 个比特记为 $r[i][j]$。 对所有的比特序列 $d_0, d_1, \ldots , d_{l - 1}$（具有某个长度 $l$），该序列的整数值等于 $2^0 \cdot d_0 + 2^1 \cdot d_1 + \cdots + 2^{l - 1} \cdot d_{l - 1}$。我们说存储在某个寄存器中的整数值就是寄存器中比特序列的整数值，也就是说，该整数值为 $2^0 \cdot r[i][0] + 2^1 \cdot r[i][1] + \cdots + 2^{b - 1} \cdot r[i][b - 1]$。 该处理器有 $9$ 种类型的指令，可以用来修改寄存器中的比特。每条指令操作一个或多个寄存器，并将其输出存储到其中的一个寄存器。下面我们用 $x := y$ 表示一个修改 $x$ 的值并将其变成 $y$ 的操作。每种类型的指令所做的操作描述如下： $\operatorname{\mathit{move}}(t, y)$：将寄存器 $y$ 中的比特数组拷贝到寄存器 $t$。对所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := r[y][j]$。 $\operatorname{\mathit{store}}(t, v)$：设置寄存器 t 等于 $v$，这里 $v$ 是某个 $b$ 个比特的数组。对于所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := v[j]$。 $\operatorname{\mathit{and}}(t, x, y)$：取寄存器 $x$ 和 $y$ 的按位与，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），如果 $r[x][j]$ 和 $r[y][j]$ 同时为 $1$ 则设置 $r[t][j] := 1$，否则设置 $r[t][j] := 0$。 $\operatorname{\mathit{or}}(t, x, y)$：取寄存器 $x$ 和 $y$ 的按位或，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），如果 $r[x][j]$ 和 $r[y][j]$ 至少有一个为 1 则设置 $r[t][j] := 1$，否则设置 $r[t][j] := 0$。 $\operatorname{\mathit{xor}}(t, x, y)$：取寄存器 $x$ 和 $y$ 的按位异或，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），如果 $r[x][j]$ 和 $r[y][j]$ 恰好有一个为 1 则设置 $r[t][j] := 1$，否则设置 $r[t][j] := 0$。 $\operatorname{\mathit{not}}(t, x)$：取寄存器 $x$ 的按位非，并将结果存到寄存器 $t$ 中。对于所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := 1 - r[x][j]$。 $\operatorname{\mathit{left}}(t, x, p)$：左移寄存器 $x$ 中的所有比特 $p$ 位，并将结果存到寄存器 $t$ 中。将寄存器 $x$ 中的比特左移 $p$ 位的结果，是一个包含 $b$ 个比特的数组 $v$。对于所有的 $j$（$0 \le j \le b - 1$），如果 $j \ge p$ 则 $v[j] = r[x][j - p]$，否则 $v[j] = 0$。对所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := v[j]$。 $\operatorname{\mathit{right}}(t, x, p)$：右移寄存器 $x$ 中的所有比特 $p$ 位，并将结果存到寄存器 $t$ 中。将寄存器 $x$ 中的比特右移 $p$ 位的结果，是一个包含 $b$ 个比特的数组 $v$。对于所有的 $j$（$0 \le j \le b - 1$），如果 $j \le b - 1 - p$ 则 $v[j] = r[x][j + p]$，否则 $v[j] = 0$。对所有的 $j$（$0 \le j \le b - 1$），设置 $r[t][j] := v[j]$。 $\operatorname{\mathit{add}}(t, x, y)$：将寄存器 $x$ 和 $y$ 中的整数值加起来，并将结果存到寄存器 $t$ 中。加法是在模 $2^b$ 下做的。正式一些来说，设 $X$ 是操作前存在寄存器 $x$ 中的整数值，而 $Y$ 是操作前存在寄存器 $y$ 中的整数值。设 $T$ 为操作后存在寄存器 $t$ 中的整数值。如果 $X + Y < 2^b$，设置 $t$ 中的比特使得 $T = X + Y$。否则，设置 $t$ 中的比特使得 $T = X + Y - 2^b$。 Christopher 希望你用这个新处理器解决两种任务。任务的类型用整数 $s$ 来表示。对所有类型的任务，你需要创建一个程序，其为上文所定义的指令构成的序列。 程序的输入包括 $n$ 个整数 $a[0], a[1], \ldots , a[n - 1]$，而每个整数都有 $k$ 个比特，也就是说，$a[i] < 2^k$（$0 \le i \le n - 1$）。在程序执行前，输入的所有的数都依次存储在寄存器 $0$ 中，使得对所有的 $i$（$0 \le i \le n - 1$），$k$ 比特序列 $r[0][i \cdot k], r[0][i \cdot k + 1], \ldots , r[0][(i + 1) \cdot k - 1]$ 的整数值等于 $a[i]$。注意 $n \cdot k \le b$。寄存器 $0$ 中所有其他的比特（其下标在 $n \cdot k$ 和 $b - 1$ 之间，包括 $n \cdot k$ 和 $b - 1$），以及其他所有寄存器中的所有比特，都初始化为 $0$。 执行某个程序就是按序执行其所包含的指令。在最后一条指令执行完毕后，程序的输出将根据寄存器 $0$ 中比特最终的值计算出来。具体来说，输出是 $n$ 个整数 $c[0], c[1], \ldots , c[n - 1]$ 的序列，这里对所有 $i$（$0 \le i \le n - 1$）来说，$c[i]$ 都是寄存器 $0$ 中比特 $i \cdot k$ 到 $(i + 1) \cdot k - 1$ 所构成的序列的整数值。注意，在程序运行结束后，寄存器 $0$ 中其余的比特（下标不小于 $n \cdot k$），以及其他寄存器中的所有比特，可能是任意值。 第一个任务（$s = 0$）是要找出输入整数 $a[0], a[1], \ldots , a[n - 1]$ 中的最小值。 具体来说，$c[0]$ 必须是 $a[0], a[1], \ldots , a[n - 1]$ 中的最小值。$c[1], c[2], \ldots , c[n - 1]$ 的值可以是任意的。 第二个任务（$s = 1$）是要将输入整数 $a[0], a[1], \ldots , a[n - 1]$ 进行非降序排序。具体来说，对于所有的 $i$（$0 \le i \le n - 1$），$c[i]$ 应当等于 $a[0], a[1], \ldots , a[n - 1]$ 中第 $1 + i$ 小的整数（也就是说，$c[0]$ 是输入整数中的最小整数）。 请帮 Christopher 写一下解决这些任务的程序。每个程序至多只能包含 $q$ 条指令。

你要实现如下函数： ```cpp void construct_instructions(int s, int n, int k, int q) ``` - $s$：任务类型。 - $n$：输入中的整数的数量。 - $k$：输入中的每个整数的比特数。 - $q$：允许的最大的指令数。 该函数将被恰好调用一次，并应当为所要解决的任务创建一个指令序列。 该函数应当调用以下函数中的一或多个，以创建指令序列： ```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) ``` - 每个函数分别往程序追加一条 $\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)$ 或 $\operatorname{\mathit{add}}(t, x, y)$ 指令。 - 对于所有相关的指令，$t$、$x$、$y$ 必须至少为 $0$ 且至多为 $m - 1$。 - 对于所有相关的指令，$t$、$x$、$y$ 不必是两两之间不同的。 - 对于指令 `left` 和 `right`，$p$ 必须至少为 $0$ 且至多为 b。 - 对于指令 `store`，$v$ 的长度必须为 $b$。 你还可以调用以下函数，以帮助测试你的答案： ```cpp void append_print(int t) ``` - 在评测你的答案时，对该函数的所有调用都将被忽略。 - 在评测程序示例中，该函数将往程序追加一个 $\operatorname{\mathit{print}}(t)$ 操作。 - 当评测程序示例在执行某个程序过程中遇到一个 $\operatorname{\mathit{print}}(t)$ 操作时，它会打印出由寄存器 $t$ 中前 $n \cdot k$ 比特构成的 $n$ 个 $k$-比特整数。 - $t$ 必须满足 $0 \le t \le m - 1$。 - 对该函数的任何调用，都不会算到你所创建的指令的数量里面。 在追加最后一条指令之后，`construct_instructions` 应当返回。随后你创建的程序将在一定数量的测试用例上评测，其中每个测试用例给出的输入数据为 $n$ 个 $k$-比特整数 $a[0], a[1], \ldots , a[n - 1]$。如果程序对给定输入数据的输出结果 $c[0], c[1], \ldots , c[n - 1]$ 满足如下条件，你的答案就将被视为通过了对应的样例： - 如果 $s = 0$，$c[0]$ 应当为 $a[0], a[1], \ldots , a[n - 1]$ 中的最小值。 - 如果 $s = 1$，对所有 $i$（$0 \le i \le n - 1$）来说，$c[i]$ 应当是 $a[0], a[1], \ldots , a[n - 1]$ 中第 $1 + i$ 小的整数。 在评测你的答案时，可能会给出下面的错误信息之一： - `Invalid index`：在调用某些函数时的参数 $t$、$x$ 或 $y$ 所给出的寄存器下标是不正确的（可能是负数）。 - `Value to store is not b bits long`：提供给 `append_store` 的 $v$ 的长度不等于 $b$。 - `Invalid shift value`：提供给 `append_left` 或 `append_right` 的 $p$ 的值不在 $0$ 和 $b$ 之间（包括 $0$ 和 $b$）。 - `Too many instructions`：你的函数试图追加超过 $q$ 条指令。

无

对于所有数据： - $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$（对于所有 $0 \le i \le n - 1$） 子任务| 分值| 特殊限制 :-:|:-:|:-: $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$ 感谢 @[Bingxiu](https://www.luogu.com.cn/user/676498) 提供交互库。附件中的交互库可用于本地测试，与实际评测用的交互库有所不同。