P14354 [集训队互测 2025] 怦然心动

Some of us get dipped in flat, some in satin, some in gloss. But every once in a while you find someone who's iridescent, and when you do, nothing will ever compare. [Flipped](https://www.bilibili.com/bangumi/play/ep291708) **这是一道交互题，仅支持 C++ 提交。在洛谷上提交该试题时，请使用不低于 C++17 的语言标准，无需引入头文件 flipped.h，而是在程序开头添加 `std::pair move(int t,int x); `**。

小 $\delta$ 需要陪小 $\tau$ 去购物。小 $\tau$ 想要买一件衣服和一条裤子。商场里有 $n$ 件衣服，价格分别为 $a_0, a_1, \cdots, a_{n-1}$，以及 $m$ 条裤子，价格分别为 $b_0, b_1, \cdots, b_{m-1}$。 小 $\tau$ 希望买到尽可能贵的衣物，但最终是小 $\delta$ 结账，而小 $\delta$ 不希望花太多的钱。因此，两人决定在购物之前通过一个游戏决定需要买什么东西。 这个游戏由两人交替行动，小 $\tau$ 先手，初始时候选清单包括商场里的所有衣服和裤子。每次操作的人会选择一件衣服或一条裤子，并将它从候选清单中永久删除。两人事先约定好了一个阈值 $B$，表示小 $\delta$ 能接受的最大价格。游戏的胜负判定标准如下： 1. 如果在任意时刻，不存在任何衣服，或不存在任何裤子了，那么他们只能不去购物。此时小 $\delta$ 不会破产，但小 $\tau$ 没有买到她想要的衣物，因此视作小 $\delta$ 获胜。 2. 否则如果在任意时刻，对于所有从剩余的衣服与裤子中分别选择一件的方案，都满足衣服和裤子的价格之和 $\leq B$，小 $\delta$ 可以在不破产的情况下满足 $\tau$ 的要求，但小 $\tau$ 不得不接受质量稍差的衣物，因此视作小 $\delta$ 获胜。 3. 否则如果在任意时刻，对于所有从剩余的衣服与裤子中分别选择一件的方案，都满足衣服和裤子的价格之和 $> B$，小 $\delta$ 会意识到他无法拥有足够多的钱以满足小 $\tau$。但由于小 $\tau$ 对于他非常重要，他只得四处借钱去结账，但此时小 $\tau$ 会很开心，因此视作小 $\tau$ 获胜。 形式化地，每次可以选择一个 $a_i (0 \leq i < n)$ 或者 $b_i (0 \leq i < m)$，并将其从对应序列中删除（并将 $n, m$ 对应地 $-1$）。如果任意时刻 $n = 0$ 或 $m = 0$ 或 $\forall_{0 \leq i < n, 0 \leq j < m} a_i + b_j \leq B$，则小 $\delta$ 获胜。否则如果任意时刻 $\forall_{0 \leq i < n, 0 \leq j < m} a_i + b_j > B$，则小 $\tau$ 获胜。 请注意，如果没有人操作时的初始局面满足某个判定标准，则游戏会依据该判定标准直接结束。 现在小 $\delta$ 已经列出了所有 $a_i$ 和 $b_j$，他想在游戏开始前知道，能够使得他保证获胜的最小阈值 $B$，这样他才能提前准备好足够的钱。有些时候，他还希望你给出一个具体的游戏过程，使得他能够赢下游戏。 ### 实现细节 你不需要也不应该实现主函数。你需要实现以下函数： ```cpp int solve(std::vector a,std::vector b); ``` 这个函数需要返回给定局面的最小阈值 $B$。$a, b$ 即为题面中给定的初始序列 $\{a_i\}$ 与 $\{b_i\}$。**保证给定的序列按照单调递增顺序排序。** 你还需要实现函数： ```cpp void play(std::vector a,std::vector b,int B); ``` 在这个函数中，你需要与交互库玩游戏，其中 $a, b$ 为给定的初始序列 $\{a_i\}$ 与 $\{b_i\}$，$B$ 为给定的阈值。**保证给定的序列按照单调递增顺序排序。** 你可以调用函数 ```cpp std::pair move(int t,int x); ``` 进行一步操作，并获得交互库的下一步操作。其中 $t = 0$ 表示你选择了序列 $a$，$t = 1$ 表示你选择了序列 $b$，而 $x$ 表示你选择的是对应序列中的第几个元素（编号从 0 开始）。交互库会返回一个 `std::pair` $(t, x)$，含义如下： 1. 如果 $(t, x) = (-1, -1)$，则表示你的操作不合法，或游戏已经结束（无论是你操作后结束，还是交互库再操作后结束），此时你应该直接返回。 2. 否则 $(t, x)$ 用和之前一样的格式表示了先手进行的下一步操作。你需要继续进行交互的过程。 请注意，在删除一个元素后，剩余的元素会按照原来的顺序拼接形成一个新的序列，所有操作的下标均按照最新的序列中的下标表示。 具体的游戏过程如下： 首先，你需要判定小 $\delta$（后手）是否能够获胜。如果你认为不能获胜，请调用一次 $\text{move}(0, 0)$ 并返回（此时 $\text{move}$ 函数的返回值并不重要）。特别地，如果在游戏开始前小 $\tau$ 已经获胜，同样视作这种情况。 否则，请调用一次 $\text{move}(1, 0)$，交互库会按照之前的格式返回交互库的第一步操作。特别地，如果游戏开始之前，小 $\delta$ 已经获胜了，交互库会返回 $(-1, -1)$，此时请在调用 $\text{move}(1, 0)$ 后立即返回。 在这之后，你需要不断调用 $\text{move}$ 来与交互库进行游戏，直到交互库返回 $(-1, -1)$。注意你不需要判定游戏是否结束，交互库会自动帮你判定。 在一组测试数据中可能会多次调用 $\text{solve}$ 或 $\text{play}$ 函数，不同的调用之间可能会保留对全局变量的修改，请注意多测清空问题。 下发文件中提供了一个参考实现 flipped.cpp。这个程序对于求值部分会返回 $114514$，而对于交互部分，会始终认为有解，并选择某个序列的最后一个元素将其删除。可以参考样例程序理解交互过程。 ### 测试程序方式 下发文件中提供了一个交互库的参考实现 grader.cpp。最终测试时所用的交互库实现与该实现不同，因此选手的解法不应依赖交互库的具体实现。 你需要在本题目录下使用以下编译命令得到可执行程序： ```cpp g++ flipped.cpp grader.cpp -o flipped -O2 ``` 样例交互库将按照如下格式进行测试： 首先读入一个变量 $o = 0/1$，其中 $o = 0$ 表示进行的是求值部分的测试，$o = 1$ 表示进行的是交互部分的测试。 接下来，如果 $o = 0$，则： - 读入一个整数 $T$，表示测试数据组数，对于每组数据： - 读入两个整数 $n, m$，表示两个序列的大小。 - 接下来一行读入 $n$ 个单调递增的整数 $a_1, a_2, \cdots, a_n$，表示传入的序列 $a$。 - 接下来一行读入 $m$ 个单调递增的整数 $b_1, b_2, \cdots, b_m$，表示传入的序列 $b$。 - 交互库会自动帮你调用 $\text{solve}(a, b)$，并将返回的结果写入标准输出。 如果 $o = 1$，则： - 读入一个整数 $T$，表示测试数据组数，对于每组数据： - 读入四个整数 $n, m, B, t$，表示两个序列的大小，给定的阈值 $B$，以及 $t = 0/1$ 表示当前局面是否为后手必胜（$t = 1$ 则后手必胜，$t = 0$ 则先手必胜）。 - 接下来一行读入 $n$ 个单调递增的整数 $a_1, a_2, \cdots, a_n$，表示传入的序列 $a$。 - 接下来一行读入 $m$ 个单调递增的整数 $b_1, b_2, \cdots, b_m$，表示传入的序列 $b$。 - 交互库会调用 $\text{play}(a, b, B)$ 并与你进行交互，对于每组数据，交互库的输出如下： - 如果你在第一次调用时没有正确判定是否必胜，交互库会输出 $\text{Wrong Answer}$。 - 如果你的操作不合法，交互库会输出 $\text{Invalid Operation: MESSAGE}$，其中 $\text{MESSAGE}$ 为用英文表达的不合法原因。如不理解英文，请自行查看 $\text{grader.cpp}$。 - 如果你的所有操作均合法，但最终没有获胜（包括在游戏没有结束时提前返回），交互库会输出 $\text{You didn't win}$。 - 如果你的所有操作均合法，且最终获胜，交互库会输出 $\text{OK}$。 请注意，由于题目保证了传入 $\text{solve}$ 的 $a, b$ 序列均递增排列，请保证输入的 $a, b$ 也按照递增顺序排列，否则可能会出现不可预料的结果。同时，如果你尝试进行不合法的交互行为，也可能会出现不可预料的结果，所有潜在的后果请自行承担。 样例交互库使用的策略是非常简单的，你可以根据自己的需求自行改动样例交互库的策略。最终评测时，交互库会使用不一样的策略，但请注意，**最终评测时，交互库不一定会使用最优策略**，你的代码需要能够应对任何交互库可能的操作。

见【测试程序方式】。

见【测试程序方式】。

选手不应该通过非法方式获得交互库的内部信息，或者以任何形式攻击交互库（包括但不限于与标准 IO 进行交互），这种行为视为作弊。 保证在所有操作合法的情况下，交互库不会使用超过 $0.5$s 的时间，也不会使用超过 $128$MB 的空间。也即，你至少有 $1.5$s 的时间和 $384$MB 的内存可以使用。 对于所有数据，满足 $1 \leq T \leq 10^5$, $n, m \geq 1$, $2 \leq \sum n + m \leq 5 \times 10^5$, $1 \leq a_i, b_i \leq 10^9$, $1 \leq B \leq 2 \times 10^9$。 下表中给出了所有子任务的数据范围，表格中的数字表示对应子任务的分值。其中： - “求值”一列对应的子任务中，交互库仅会调用 $\text{solve}$ 函数，你能够获得分数当且仅当对于该子任务的所有 $\text{solve}$ 函数都返回了正确的结果。 - “交互”一列对应的子任务中，交互库仅会调用 $\text{play}$ 函数，你能够获得分数当且仅当对于该子任务的所有 $\text{play}$ 的调用，都能正确判定游戏的结果，且对于可以获胜的数据，能够成功完成游戏并最终获胜。 本题采用子任务捆绑测试，有子任务依赖。具体地，每个子任务将依赖所有在其左上方的子任务。特别地，这意味着所有交互部分的子任务会依赖与其数据规模相同的求值部分子任务。 在洛谷评测中，子任务编号将从左上至右下依次编号为 $1 \sim 10$（例如第三档部分分的交互部分子任务编号为 $6$）。 | $n + m \leq$ | $\sum n + m \leq$ | 求值 | 交互 | | :--: | :--: | :--: | :--: | | $50$ | $1000$ | $3$ | $2$ | | $500$ | $5000$ | $13$ | $7$ | | $2500$ | $10^4$ | $15$ | $10$ | | $10^5$ | $5 \times 10^5$ | $14$ | $8$ | | $5 \times 10^5$ | $5 \times 10^5$ | $12$ | $16$ |