魔术戏法 - 题目

Alicia 和 Beatriz 正在为 IOI 才艺表演准备一个魔术。魔术的流程如下：

志愿者选择一个长度为 $N$ 的排列 $P$，并将 $N$ 张牌放在桌子上。牌的编号从 $0$ 到 $N - 1$，其中第 $i$ 张牌上显示的数值为 $P[i]$。
Alicia 进入房间，观察这些牌，并选择其中的 $K$ 张牌将其翻转至背面，从而隐藏它们的数值。
Beatriz 随后进入房间，观察牌当前的排列情况（包括哪些牌是背面朝上的），并神奇地推断出所有 $K$ 张被隐藏牌的数值！

你的任务是为 Alicia 和 Beatriz 设计并实现一种策略。魔术越令人印象深刻，你的得分就越高：目标是最大化 $K$，即 Beatriz 能够正确揭示的被隐藏牌的数量。

你需要实现以下第一个过程：

std::vector<int> Alicia(std::vector<int> P)

该过程应返回一个长度为 $N$ 的数组 $Q$，表示 Alicia 执行的翻牌操作。对于每个索引 $i$ ($0 \le i \le N - 1$)，数组 $Q$ 中的值必须按如下方式设置：

你需要实现以下第二个过程：

std::vector<int> Beatriz(std::vector<int> Q)

该过程应返回一个长度为 $N$ 的数组 $B$，表示原始排列 $P$，即对于每个 $i$ ($0 \le i \le N - 1$)，都应满足 $B[i] = P[i]$。

在每个测试用例中，这两个过程各被调用恰好一次，流程如下：

在程序的第一次运行期间：
- 使用原始排列 $P$ 调用 Alicia。
- 对于 Alicia 返回的数组 $Q$：
  - 如果数组不符合上述约束，你将收到 Output isn't correct 的判决。
  - 否则，数组 $Q$ 将由评分系统存储。
在程序的第二次运行期间：
- 使用数组 $Q$ 调用 Beatriz。

令 $M$ 为你的解决方案在所有测试用例中成功完成魔术所需的最小 $K$ 值。

考虑 $N = 6$ 且 $P = [2, 4, 3, 1, 5, 6]$ 的场景。调用 Alicia 的方式如下：

Alicia([2, 4, 3, 1, 5, 6])

假设 Alicia 使用以下策略：翻转所有满足 $P[i] = i + 1$ 的牌 $i$。在这种情况下，该条件对 $i = 2, 4, 5$ 成立。因此，该过程返回数组 $[2, 4, -1, 1, -1, -1]$。

现在，调用 Beatriz 的方式如下：

Beatriz([2, 4, -1, 1, -1, -1])

了解 Alicia 的策略后，她找到并返回了原始数组 $P = [2, 4, 3, 1, 5, 6]$。

在这种情况下，$K = 3$，因为有三张牌被翻转。然而，如果提交此策略，得分将为 0，因为存在某些排列使得没有任何索引 $i$ 满足 $P[i] = i + 1$。

注意，此样例不满足 $N = 256$ 的约束，因此不会在评分中使用。该任务的可下载附件中包含一个 $N = 256$ 的评分器样例输入。在评估过程中，子任务 0 使用了相同的排列 $P$。

输入格式：

N
P[0] P[1] ... P[N-1]

输出格式：

S
Q[0] Q[1] ... Q[S-1]
T
B[0] B[1] ... B[T-1]

这里：

注意，虽然本任务中所有测试用例均满足 $N = 256$，但你可以使用任意 $N$ 值来测试样例评分器。

QOJ.ac