背景

https://www2.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4.pdf

本题仅允许使用 C++ 提交。因为需要较新版本的编译器，也请不要使用 C++14 (GCC 9)。

洛谷不允许提交两个代码分别运行，所以需要你在提交时把代码合并。与原题不一样的是，你不需要提交两个文件，只需要实现题面中的四个函数。模板代码如下。

// 这里可以放你需要的头文件
// 这里可以放你需要的全局变量，注意 A 和 B 不共享这些变量，但是 A 的两个函数共享，B 的两个函数共享
extern "C" void InitA(int T, int X);
extern "C" int GameA(int I, int J);
extern "C" void InitB(int T);
extern "C" int GameB(int I, int J);

保证若无非法操作，交互库占用内存小于 2MB，占用时间小于 50ms。

题目描述

入选日本信息学奥林匹克竞赛（JOI）代表队的 A 君和 B 君，为了提高信息处理技术，决定与信息学奥林匹克日本委员会的 K 理事长进行一场“信使游戏”。以下是该游戏的规则。

A 君和 B 君被分别隔离在不同的房间中，如图所示。A 君、B 君和 K 理事长的房间内各设有一部内线电话，但只有 K 理事长可以拨打电话。除此之外的其他联系方式均被切断，除非接到指示，否则 A 君和 B 君不得离开房间。

模式图：

A 君的房间 | 长走廊 | K 理事长的房间 | 长走廊 | B 君的房间

游戏开始时，K 理事长通过电话告诉 A 君一个正整数 $X$。游戏的目的是在 A 君和 B 君不进行直接联系的情况下，由 A 君将 $X$ 的值正确传达给 B 君。

K 理事长的房间内有一个 $4 \times 4$ 的网格。将第 $i$ 行第 $j$ 列的格子表示为 $(i, j)$（$1 \le i \le 4, 1 \le j \le 4$）。格子 $(1, 1)$ 为左上角，$(1, 4)$ 为右上角，$(4, 1)$ 为左下角，$(4, 4)$ 为右下角。游戏开始时，一枚棋子会被放置在某个格子上。此后，K 理事长不会改变棋子的位置。

接下来，K 理事长会反复通过电话呼叫 A 君或 B 君到他的房间。每当 A 君或 B 君来到 K 理事长的房间时，必须将棋子向上下左右四个方向中的任意一个相邻格子移动。移动棋子后，A 君或 B 君返回各自的房间。如果 B 君来到 K 理事长的房间时已经知道了 $X$ 的值，则可以选择不移动棋子，而是直接向 K 理事长回答 $X$ 的值。如果回答的 $X$ 值正确，则判定为获胜，否则判定为失败。

K 理事长呼叫 A 君或 B 君的时机是不规则的，A 君和 B 君不知道 K 理事长呼叫两人的顺序。但是，K 理事长在游戏开始时已经决定了呼叫顺序，并且保证 K 理事长不会连续呼叫同一人超过 $100$ 次。如果在 K 理事长总共呼叫 A 君和 B 君 $10000$ 次后，A 君或 B 君回到各自房间时 B 君仍未回答 $X$ 的值，则判定为失败并结束游戏。

---

本处与本题评测时有略微不同。

实现细节

你必须使用同一种编程语言提交两个文件。

第一个文件：playerA.c 或 playerA.cpp

该文件实现了 A 君的策略，必须实现以下例程：

• void InitA(int T, int X)

  • 该例程在最开始仅被调用一次。
  • 参数 $T$ 为子任务编号。
  • 参数 $X$ 是 A 君需要传达给 B 君的正整数。

• int GameA(int I, int J)

  • 当 A 君被呼叫到 K 理事长的房间时，该例程会被调用。
  • 参数 $I, J$ 表示 A 君来到房间时棋子所在的格子 $(I, J)$，满足 $1 \le I \le 4$ 且 $1 \le J \le 4$。
  • 该例程必须返回整数 $-1, -2, -3, -4$ 中的任意一个。如果返回其他值，则判定为失败 [1] 并终止程序运行。这些返回值代表 A 君执行以下操作：
    • $-1$：将棋子移动到上方的格子 $(I - 1, J)$。
    • $-2$：将棋子移动到下方的格子 $(I + 1, J)$。
    • $-3$：将棋子移动到左方的格子 $(I, J - 1)$。
    • $-4$：将棋子移动到右方的格子 $(I, J + 1)$。
  • 如果指定的移动导致棋子移出棋盘，则判定为失败 [2] 并终止程序运行。

第二个文件：playerB.c 或 playerB.cpp

该文件实现了 B 君的策略，必须实现以下例程：

• void InitB(int T)

  • 该例程在最开始仅被调用一次。
  • 参数 $T$ 为子任务编号。

• int GameB(int I, int J)

  • 当 B 君被呼叫到 K 理事长的房间时，该例程会被调用。
  • 参数 $I, J$ 表示 B 君来到房间时棋子所在的格子 $(I, J)$，满足 $1 \le I \le 4$ 且 $1 \le J \le 4$。
  • 该例程必须返回整数 $-1, -2, -3, -4$ 中的任意一个，或者一个正整数 $Y$。如果返回其他值，则判定为失败 [3] 并终止程序运行。这些返回值代表 B 君执行以下操作：
    • $-1$：将棋子移动到上方的格子 $(I - 1, J)$。
    • $-2$：将棋子移动到下方的格子 $(I + 1, J)$。
    • $-3$：将棋子移动到左方的格子 $(I, J - 1)$。
    • $-4$：将棋子移动到右方的格子 $(I, J + 1)$。
    • 正整数 $Y$：向 K 理事长回答 $X$ 的值为 $Y$。此时，若 $X = Y$ 则判定为获胜，否则判定为失败 [5] 并终止程序运行。
  • 如果指定的移动导致棋子移出棋盘，则判定为失败 [4] 并终止程序运行。

重要限制与说明

• 例程 GameA 和 GameB 不会被其中一方连续调用超过 $100$ 次。
• 如果在 GameA 和 GameB 总共被调用 $10000$ 次时 GameB 仍未返回正整数，则判定为失败 [6] 并终止程序运行。
• 你可以自由实现其他辅助例程或声明全局变量。但由于提交的两个程序会与评分程序链接成一个可执行文件，因此必须将每个文件中的所有全局变量和内部例程声明为 static，以避免与其他文件产生冲突。
• 在评分时，该程序会作为 A 君侧和 B 君侧两个进程运行，因此 A 君侧和 B 君侧无法共享程序中的全局变量。
• 你的提交不得通过标准输入输出或其他任何方式进行交互。

---

编译与运行方法

用于测试程序的评分程序示例包含在可从竞赛网站下载的压缩包中。该压缩包中也包含了必须提交的文件示例。

评分程序示例由一个文件组成，即 grader.c 或 grader.cpp。要测试编写的程序，请执行以下命令：

• C 语言：gcc -O2 -lm grader.c playerA.c playerB.c -o grader
• C++ 语言：g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader

编译成功后，将生成名为 grader 的可执行文件。

请注意：实际的评分程序与示例评分程序不同。示例评分程序作为单个进程启动，从标准输入读取数据，并将结果输出到标准输出。

---

在本题真正评测时，你可以理解评测机仍然会按照类似两个程序一样运行，但是在一个进程中不会运行 A 君的两个函数和或 B 君的两个函数。

输入格式

注意这是评测器输入格式。

评分程序示例从标准输入读取以下内容：

• 第 1 行包含整数 $T, X, I_0, J_0$，以空格分隔，分别表示：
  • 子任务编号 $T$
  • A 君需要传达给 B 君的整数 $X$
  • 游戏开始时棋子的位置 $(I_0, J_0)$
• 第 2 行包含一个长度恰好为 10 000 的字符串，由字符 A 和 B 组成。若第 $k$ 个字符 ($1 \le k \le 10 000$) 为 A 或 B，则表示在 InitA 和 InitB 调用后，第 $k$ 次调用的例程分别为 GameA 或 GameB。

输出格式

注意这是示例评测器输格式。

如果程序正常结束，评分程序示例会将以下信息输出到标准输出：

• 如果获胜，输出 Accepted。
• 如果失败，根据“实现细节”一节中提到的编号输出失败类型，例如 Wrong Answer [1]。
• 此外，对于失败 [5]，会同时输出正确的 $X$ 值以及 GameB 返回的正整数 $Y$ 的值，格式为 Wrong Answer [5] : X = 2, Y = 3。

提示

A 君侧		B 君侧
调用	返回值	调用	返回值
InitA(2, 6)		InitB(2)
GameA(1, 1)	-2
		GameB(2, 1)	-4
		GameB(2, 2)	-2
GameA(3, 2)	-3
GameA(3, 1)	-1
		GameB(2, 1)	6

---

数据范围

• 所有输入数据满足：$1 \le X \le 1 000 000 000$

子任务

子任务 1 [20 分]

• 满足 $T = 1$。
• 首先被呼叫到 K 理事长房间的是 A 君，且 A 君和 B 君交替被呼叫。即在 InitA 和 InitB 调用后，例程按 GameA, GameB, GameA, GameB, ... 的顺序被调用。

子任务 2 [20 分]

• 满足 $T = 2$。
• 游戏开始时棋子的位置为 $(I_0, J_0) = (1, 1)$。即在 InitA 和 InitB 调用后，首先以 $I = 1, J = 1$ 为参数调用 GameA 或 GameB。

子任务 3 [60 分]

• 满足 $T = 3$。

---

题目来源：https://www2.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day4.pdf。

翻译来源：QOJ。