P11344 [KTSC 2023 R1] 会议室

**在洛谷提交本题时的一些注意事项（与原题面不同之处请以此处为准）：** 1. 提交时请不要添加 `workshop.h`，请在程序开头加入如下函数声明语句： ```cpp void init(); int morning(int my_num, int right_num); int afternoon(int left_num, int my_num, int right_num); int evening(int left_num, int my_num, int right_num); ``` 2. 本题仅支持 C++ 语言（包括 `C++17`，`C++20`，`C++23`）提交。

$N$ 名魔法师聚在一起，为了增进友谊并交流彼此的魔法，他们决定举办一场郊游。在这个郊游会上玩一天有趣的游戏。 游戏在一个巨大的会议室里进行。这个会议室有一张有 $N$ 个座位的圆桌。圆桌上的每个座位都长得一样，魔法师也都长得一样，无法区分彼此。不允许进行任何言语交流。 游戏分三个阶段进行，每个阶段如下： - 早上，魔法师们围坐在圆桌旁。每个座位上都放着一张空白纸条，以及一张写有 $0$ 到 $N-1$ 之间某个整数的纸条，每个座位上的整数都互不相同。每位魔法师都可以看到自己以及坐在自己右边的魔法师座位上的整数。以此为基础，魔法师会在空白纸条上写下一个 $0$ 到 $10^9-1$ 之间的整数。这个整数写得很小心，只有自己才能看到。之后，把刚才写了整数的纸条折起来放在座位上，并拿着最初放在座位上的那张数字纸条离开会议室。 - 中午，魔法师们围坐在圆桌旁。每个座位上都放着一张空白纸条，以及早上自己写下数字的那张纸条。每位魔法师可以看到自己、坐在自己左边以及右边的魔法师纸条上写着的整数。以此为基础，魔法师会在空白纸条上写下一个 $0$ 到 $10^9-1$ 之间的整数。这个整数写得很小心，只有自己才能看到。之后，把刚才写了整数的纸条折起来放在座位上，并拿着早上写的纸条离开会议室。 - 晚上，魔法师们围坐在圆桌旁。每个座位上都放着一张空白纸条，以及中午自己写下数字的那张纸条。每位魔法师可以看到自己、坐在自己左边以及右边的魔法师纸条上写着的整数。以此为基础，魔法师会在空白纸条上写下一个 $0$ 到 $39$ 之间的整数。这个整数写得很小心，只有自己才能看到。之后，把刚才写了整数的纸条折起来放在座位上，并拿着中午写的纸条离开会议室。 每次离开会议室后，魔法师手中的纸条都会因魔法的力量而消失，且魔法师会忘记在会议室所做的一切。早上，中午，晚上每个魔法师坐的位置都是一样的。 魔法师们不知道 $N$，但知道 $10\leq N \leq 10^5$。 游戏结束后，郊游的组织者会展开所有留在座位上的纸条。如果圆桌上任意相邻座位上纸条写的数字都互不相同，则魔法师们获胜。此外，游戏结束时（即晚上结束时）纸条上留下的数字的最大值越小越好。 魔法师们在游戏进行中什么都不能说，但他们可以达成协议，在游戏进行之前使用共同的策略。请你替魔法师们想出一个策略，使得他们在赢得游戏的前提下，最终纸条上的数字尽可能小。 ### 实现细节 你需要实现以下函数。 ```cpp void init(); ``` - 该函数只被调用一次，在调用其他所有函数之前被调用。 - 如果以后有调用函数所需的前处理或全局变量设置，可以在该函数中实现。 ```cpp int morning(int my_num, int right_num); ``` - `my_num`：早上该魔法师所在座位的纸条上的整数 - `right_num`：早上该魔法师右边座位的纸条上的整数 - 该函数必须返回一个整数，该整数将由该魔法师在早上写到空白纸条上。此函数的返回值必须在 $[0, 10^9 - 1]$ 范围内。 - 此函数的返回值必须仅依赖于 `my_num` 和 `right_num` 的值。 - 函数最多被调用 $2\times 10^6$ 次。 ```cpp int afternoon(int left_num, int my_num, int right_num); ``` - `left_num`：中午该魔法师左边座位的纸条上的整数 - `my_num`：中午该魔法师所在座位的纸条上的整数 - `right_num`：中午该魔法师右边座位的纸条上的整数 - 该函数必须返回一个整数，该整数将由该魔法师在中午写到空白纸条上。此函数的返回值必须在 $[0, 10^9 - 1]$ 范围内。 - 此函数的返回值必须仅依赖于 `left_num`，`my_num` 和 `right_num` 的值。 - 函数最多被调用 $2\times 10^6$ 次。 ```cpp int evening(int left_num, int my_num, int right_num); ``` - `left_num`：晚上该魔法师左边座位的纸条上的整数 - `my_num`：晚上该魔法师所在座位的纸条上的整数 - `right_num`：晚上该魔法师右边座位的纸条上的整数 - 该函数必须返回一个整数，该整数将由该魔法师在晚上写到空白纸条上。此函数的返回值必须在 $[0, 39]$ 范围内。 - 此函数的返回值必须仅依赖于 `left_num`，`my_num` 和 `right_num` 的值。 - 函数最多被调用 $2\times 10^6$ 次。 不能在提交的源代码的任何部分运行 I/O 函数。 `morning`、`afternoon` 和 `evening` 函数的返回值必须仅依赖于给定参数的值。如果多次以相同的参数值调用函数时返回不同的值，则无论游戏胜负如何，都将被视为错误答案。 每个测试案例由多个（1 个以上）独立游戏组成。虽然不能保证 `morning`、`afternoon` 和 `evening` 函数按顺序调用，但可以保证游戏会基于函数的返回值按照题目背景中给出的方式进行。 在每个测试案例中，您的程序运行两次。在比赛系统上，执行时间由两次执行程序的执行时间之和来衡量，内存使用量也由两次执行程序的内存使用量之和来衡量。时间限制和内存限制基于两次运行结果的总和。`morning`、`afternoon` 和 `evening` 函数的调用次数约束条件也是以两次执行中的调用次数之和为基准显示的。在实际提交时，最坏的情况下，可以假设评分程序基本消耗的时间在 2 秒以内。

无

无

对于所有输入数据，满足： - $10 \le N \le 100000$。 - 在每个测试用例中，`morning` 函数最多被调用 $2000000$ 次。 - 在每个测试用例中，`afternoon` 函数最多被调用 $2000000$ 次。 - 在每个测试用例中，`evening` 函数最多被调用 $2000000$ 次。 如果在任何测试案例中，在基于 `morning`、`afternoon` 和 `evening` 函数的返回值进行游戏时，魔法师们都无法获胜，那么在这部分问题上，您将获得 $0$ 分。 详细子任务附加限制及分值如下所示。 | 子任务编号 | $N \le$ | 子任务分数 | 计分方式 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $40$ | $5$ | A | | $2$ | $100000$ | $95$ | B | A：如果顺利完成交互过程，给与 $100\%$ 的分数。 B：记 `evening` 函数的返回值加 $1$ 的最大值为 $m$，那么你的得分如下表所示。 | 条件 | 分数 | | :--: | :--: | | $10 \le m \le 40$ | $46 - m$ | | $m = 9$ | $38$ | | $m = 8$ | $41$ | | $m = 7$ | $46$ | | $m = 6$ | $52$ | | $m = 5$ | $64$ | | $m = 4$ | $76$ | | $m \le 3$ | $95$ |