P12400 [COI 2025] 人工智能 / Automatizacija（暂时无法评测）

译自 [COI 2025](https://hsin.hr/hio2025/) T1。 我们在附件中提供了模板文件，你可以在这个文件的基础上进行编辑。 （我们在研究交互库的策略，暂时无法评测。）

**这是一道通信题。** 为了方便评测，我们改为函数式交互题。 A 和 B 在玩游戏。 她们每个人都有一个大小为 $K$ 的**集合**，集合中元素为 $[1,N]$ 间的正整数（注意集合中元素两两不同）。 **A 和 B 只知道自己集合里面的元素**。游戏的目标是求出她们集合的交的大小。 A 和 B 不能直接通信，但她们可以用一块游戏板通信。我们给出通信的具体说明： - 游戏板初始时有 $N$ 个空格子。可以在空格子里面放小球。 - A 与 B 轮流在空格子中放小球，A 先操作。小球被放在空格子里面后，格子即被占据，不能再放小球。 - A 放蓝色的球，B 放红色的球。 - 在游戏全程中，A 与 B 都能实时得知游戏板的状态。 - 轮到一方操作时，有两种情况： - 仍有空格子剩余。操作方可以选择放小球，或者报告交的大小来结束游戏。 - 没有空格子了。操作方必须报告交的大小，结束游戏。 在游戏过程中，A 与 B 只能通过游戏板通信。但是在游戏开始之前，她们可以商量好游戏策略。 请你帮 A 与 B 确定一个游戏策略，使得至少有一个人能够在某一时刻正确猜出交的大小，结束游戏。 为了锻炼你的水平，我们要求你的策略用到的信息只包括当前游戏板的状态。换句话说，**你无法得知这个状态是如何转移过来的。** ### 实现细节 你需要实现两个函数。 ```cpp vector Alice(int N, int K, int T, vector S, vector states); vector Bob(int N, int K, int T, vector S, vector states); ``` 这两个函数的参数含义如下： - `N`：值域和游戏板的格子数。 - `K`：集合大小。 - `T`：该玩家可能遇到的状态数量。 - 在实际测试数据中，$T$ 严格等于可能遇到的状态数量。 - 但是在样例中，$T$ 可能比真实值小。 - `S`：一个长度为 $K$ 的数组，表示当前玩家持有的集合。 - `states`：一个长度为 $T$ 的数组，表示当前玩家可能遇到的所有状态。 - 每个状态用一个长度为 $N$ 的字符串 `state[0]~state[T-1]` 表示。 - 每个字符串 $S$ 中只有 $\texttt{P},\texttt{C},\texttt{.}$。其中，$S_{i-1}=\texttt{P}$ 代表格子 $i$ 中有蓝球，$S_{i-1}=\texttt{C}$ 代表格子 $i$ 中有红球，$S_{i-1}=\texttt{.}$ 代表格子 $i$ 是空的。 调用 Alice，表示你要确定 A 的策略；调用 Bob，表示你要确定 B 的策略。 你需要返回一个长度为 $T$ 的数组 `res`。每个元素是一个字符和一个正整数。 `res[i].first` 是字符 $\texttt{!}$ 或 $\texttt{+}$。 - 如果是 $\texttt{!}$，表示报告答案。`res[i].second` 表示报告的答案。此时，你需要保证 `res[i].second` 是 $[0,N]$ 间的一个整数。 - 如果是 $\texttt{?}$，表示放球。`res[i].second` 表示要放在哪个格子。此时，你需要保证 `res[i].second` 是 $[1,N]$ 间的一个整数，且这个格子是空的。 由于洛谷评测系统的限制，该程序将只被运行一次。如果你使用了全局变量，请注意清空。

Sample Grader 输入格式如下： 第一行，正整数 $P$。$P=1$ 表示 Alice 的输入，$P=2$ 表示 Bob 的输入。 第二行，两个正整数 $N,K$。 第三行，$K$ 个正整数，表示集合中的元素。 第四行，正整数 $T$。 接下来 $T$ 行，每行一个字符串，描述一个状态。

Sample Grader 输出 $T$ 行，每行一个操作。

### 样例解释 为了方便，样例只展示了一个可行的策略。解释如下： | 游戏板状态 | 操作 | 注记 | | :-: | :-: | :-: | | $\texttt{....}$ | $\texttt{+ 1}$ | A 在格子 $1$ 上放了一个球。 | | $\texttt{P...}$ | $\texttt{+ 3}$ | B 在格子 $3$ 上放了一个球。 | | $\texttt{P.C.}$ | $\texttt{+ 4}$ | A 在格子 $4$ 上放了一个球。 | | $\texttt{P.CP}$ | $\texttt{+ 2}$ | B 在格子 $2$ 上放了一个球。 | | $\texttt{PCCP}$ | $\texttt{! 1}$ | A 报告交集大小为 $1$，终止游戏。猜对了！| ### 数据范围 - $2\le N\le 16$； - $1\le K\le N$。 ### 子任务 - $\text{Subtask 0 (0 pts)}$：样例。 - $\text{Subtask 1 (11 pts)}$：集合包含 $K$ 个连续的正整数。 - $\text{Subtask 2 (7 pts)}$：$N$ 是偶数，集合的元素都在 $[1,N/2]$ 间。 - $\text{Subtask 3 (16 pts)}$：$N\le 4$。 - $\text{Subtask 4 (13 pts)}$：$N=14$，$K=2$。 - $\text{Subtask 5 (12 pts)}$：集合的元素都在 $[1,N-1]$ 间。 - $\text{Subtask 6 (41 pts)}$：无额外约束。