{"problem":{"name":"[JOIST 2022] 坏掉的设备 2 / Broken Device 2","description":{"content":" Anna 和 Bruno 是赌术大师。他们将和担任庄家的 D-taro 玩一个游戏。在这个游戏中，Anna 和 Bruno 分别待在不同的房间里。他们只能使用一台损坏的装置相互通信。D-taro 会给 Anna 一个整数。对于 Anna 和 Bruno 来说，这个游戏的目标是使用该装置，把给定的整数从 Anna 传递给 Bruno。 当游戏开始时，一开始，Anna 声明一个整数 $m$，其取值","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9526"},"statements":[{"statement_type":"Markdown","content":"Anna 和 Bruno 是赌术大师。他们将和担任庄家的 D-taro 玩一个游戏。在这个游戏中，Anna 和 Bruno 分别待在不同的房间里。他们只能使用一台损坏的装置相互通信。D-taro 会给 Anna 一个整数。对于 Anna 和 Bruno 来说，这个游戏的目标是使用该装置，把给定的整数从 Anna 传递给 Bruno。\n\n当游戏开始时，一开始，Anna 声明一个整数 $m$，其取值在 1 到 2 000（含）之间。然后他们进行 $Q$ 轮。第 $i$ 轮（$1 \\le i \\le Q$）按如下方式进行。\n\n1. D-taro 给 Anna 一个整数 $A_i$。\n2. Anna 向装置输入数组 $s_i, t_i$。数组 $s_i, t_i$ 的每个元素都必须为 0 或 1。数组 $s_i, t_i$ 的长度必须相同，且长度在 1 到 $m$（含）之间。\n3. 令 $u_i$ 为由数组 $s_i$ 和 $t_i$ 通过 **riffle shuffle**（见下文）得到的数组。然后装置将 $u_i$ 发送给 Bruno。\n4. Bruno 向 D-taro 发送一个整数。若该整数与 D-taro 给 Anna 的整数 $A_i$ 相同，则 Anna 和 Bruno 在本轮获胜。\n\n请编写实现 Anna 和 Bruno 策略的程序，使他们在全部 $Q$ 轮中都能获胜。\n\n### 洗牌交错（riffle shuffle）\n\n若能将数组 $Z$ 的元素划分为两组，并满足以下两个条件，则称数组 $Z$ 是由数组 $X$ 和数组 $Y$ 通过 riffle shuffle 得到的。\n\n* 由第一组元素按原有顺序组成的数组等于数组 $X$。\n* 由第二组元素按原有顺序组成的数组等于数组 $Y$。\n\n例如，数组 $Z = [1, 1, 1, 0, 0, 0]$ 可由 $X = [1, 1, 0]$ 与 $Y = [1, 0, 0]$ 通过 riffle shuffle 得到，因为由 $Z$ 的第 1、2、4 个元素按原顺序组成的数组为 $[1, 1, 0]$，而由第 3、5、6 个元素按原顺序组成的数组为 $[1, 0, 0]$。\n\n另一方面，若 $X = [1, 1, 0]$、$Y = [1, 0, 0]$，而 $Z = [0, 0, 0, 1, 1, 1]$，则数组 $Z$ 不是由 $X$ 和 $Y$ 通过 riffle shuffle 得到的。\n\n### 实现细节\n\n你需要提交两个文件。\n\n第一个文件是 `Anna.cpp`。它应实现 Anna 的策略，并实现下列函数。程序应通过预处理指令 `#include` 包含 `Anna.h`。\n\n* `int Declare()`\n\n  该函数在开始时被调用一次。\n  * 返回值是 Anna 声明的整数 $m$。\n  * 整数 $m$ 必须在 1 到 2 000（含）之间。若不满足此条件，你的程序将被判为 **Wrong Answer [1]**。\n\n* `std::pair<std::vector<int>, std::vector<int>> Anna(long long A)`\n\n  在调用 `Declare` 之后，该函数将被调用 $Q$ 次。第 $i$ 次调用（$1 \\le i \\le Q$）对应第 $i$ 轮的步骤 1 和步骤 2。\n  * 参数 $A$ 是 D-taro 给 Anna 的整数 $A_i$。\n  * 返回值是 Anna 输入到装置中的两个数组 $s_i, t_i$ 组成的二元组。\n  * 数组 $s_i, t_i$ 的每个元素都必须为 0 或 1。若不满足此条件，你的程序将被判为 **Wrong Answer [2]**。\n  * 数组 $s_i, t_i$ 的长度都必须在 1 到 $m$（含）之间。若不满足此条件，你的程序将被判为 **Wrong Answer [3]**。\n  * 数组 $s_i, t_i$ 的长度必须相同。若不满足此条件，你的程序将被判为 **Wrong Answer [4]**。\n\n第二个文件是 `Bruno.cpp`。它应实现 Bruno 的策略，并实现下列函数。程序应通过预处理指令 `#include` 包含 `Bruno.h`。\n\n* `long long Bruno(std::vector<int> u)`\n\n  在 Anna 向装置输入数组之后，该函数会被调用一次。总共，该函数会被调用 $Q$ 次。第 $i$ 次调用（$1 \\le i \\le Q$）对应第 $i$ 轮的步骤 3 和步骤 4。\n  * 参数 `u` 是装置在第 $i$ 轮发送给 Bruno 的数组 $u_i$。\n  * 返回值是 Bruno 发送给 D-taro 的整数。\n  * 返回值必须与 D-taro 给 Anna 的整数 $A_i$ 相同。若不满足此条件，你的程序将被判为 **Wrong Answer [5]**。\n\n### 重要注意事项\n\n* 你的程序可以实现其他用于内部的函数，或使用全局变量。提交的文件将与评测器一起编译，变成一个可执行文件。所有全局变量和内部函数都应当声明在未命名命名空间中，以避免与其他文件冲突。评测时会以 Anna 进程和 Bruno 进程两个进程形式运行。Anna 进程与 Bruno 进程不能共享全局变量。\n* 你的程序不得使用标准输入与标准输出。你的程序不得通过任何方式与其他文件通信。但是，你的程序可以向标准错误输出调试信息。\n\n### 编译与本地测试\n\n你可以从竞赛网页下载一个压缩包，其中包含用于本地测试你程序的样例评测器。压缩包还包含你程序的样例源代码。\n\n样例评测器为文件 `grader.cpp`。为了测试你的程序，请将 `grader.cpp`、`Anna.cpp`、`Bruno.cpp`、`Anna.h`、`Bruno.h` 放在同一目录下，并运行如下命令以编译程序。\n\n```\ng++ -std=gnu++17 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp\n```\n\n编译成功后，会生成名为 `grader` 的可执行文件。\n\n请注意，实际评测器与样例评测器不同。样例评测器以单进程形式运行，从标准输入读入数据，并将结果写到标准输出。\n\n## Input\n\n样例评测器从标准输入读取如下数据。\n\n> $Q$ \\\n> $A_1$ \\\n> $A_2$ \\\n> $\\vdots$ \\\n> $A_Q$\n\n## Output\n\n样例评测器向标准输出写出如下信息（引号仅为说明）。\n\n* 若你的程序被判定为正确，它会输出函数 `Declare` 的返回值 $m$，例如 “Accepted: 2000”。\n* 若你的程序被判定为任一类 Wrong Answer，样例评测器会写出其类型，例如 “Wrong Answer [1]”。\n\n如果你的程序同时触犯多类 Wrong Answer 的条件，样例评测器只报告其中一种。\n\n样例评测器在每一轮计算 riffle shuffle 时使用伪随机数。其结果在不同执行中不会改变。为了更改伪随机数的种子，请如下方式执行样例评测器。\n\n```\n./grader 2022\n```\n\n第一个参数应为一个整数。\n\n[samples]\n\n## Background\n\n不要引入头文件，并使用 **C++ 20** 提交。\n\n## Note\n\n#### 约束\n\n* $1 \\le Q \\le 1\\,000$。\n* $1 \\le A_i \\le 1\\,000\\,000\\,000\\,000\\,000\\,000 \\ (= 10^{18}) \\ (1 \\le i \\le Q)$。\n\n#### 子任务\n\n1. （5 分）$A_i \\le 2\\,000 \\ (1 \\le i \\le Q)$。\n2. （5 分）$A_i \\le 4\\,000\\,000 \\ (1 \\le i \\le Q)$。\n3. （3 分）$A_i \\le 10\\,000\\,000 \\ (= 10^7) \\ (1 \\le i \\le Q)$。\n4. （12 分）$A_i \\le 100\\,000\\,000 \\ (= 10^8) \\ (1 \\le i \\le Q)$。\n5. （15 分）$A_i \\le 100\\,000\\,000\\,000 \\ (= 10^{11}) \\ (1 \\le i \\le Q)$。\n6. （60 分）无限制。对于本子任务，你的得分计算如下。\n   * 令 $m^*$ 为本子任务所有测试中，Anna 声明的整数 $m$ 的最大值。\n   * 你的得分如下所示。\n\n| $m^*$ 的取值 | 分数 |\n| :--- | :--- |\n| $201 \\le m^* \\le 2\\,000$ | $40 - 25 \\times \\log_{10}\\!\\left(\\dfrac{m^*}{200}\\right)$ 分（向下取整为整数） |\n| $161 \\le m^* \\le 200$ | 40 分 |\n| $156 \\le m^* \\le 160$ | 44 分 |\n| $151 \\le m^* \\le 155$ | 48 分 |\n| $146 \\le m^* \\le 150$ | 52 分 |\n| $141 \\le m^* \\le 145$ | 56 分 |\n| $m^* \\le 140$ | 60 分 |\n\n### 样例通信\n\n下面给出样例评测器的一个样例输入以及相应的函数调用。\n\n#### 样例输入 1\n\n```\n2\n42\n2000\n```\n\n| 调用 | 返回值 |\n| :--- | :--- |\n| `Declare()` | 4 |\n| `Anna(42)` | `([0, 0, 1, 0], [1, 1, 0, 1])` |\n| `Bruno([1, 0, 0, 1, 0, 1, 0, 1])` | 42 |\n| `Anna(2000)` | `([0, 1], [0, 0])` |\n| `Bruno([0, 0, 1, 0])` | 2000 |\n\n在该样例输入中，共有 $Q \\ (= 2)$ 轮。对于第 1 轮，D-taro 给 Anna 的整数为 $A_1 \\ (= 42)$。\n\n对于第 2 轮，D-taro 给 Anna 的整数为 $A_2 \\ (= 2000)$。\n\n该样例输入满足所有子任务的约束。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9526","tags":["2022","交互题","Special Judge","通信题","JOISC/JOIST（日本）"],"sample_group":[],"created_at":"2026-03-03 11:09:25"}}