魔術戲法 - المسألة

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]$。

在每個測試案例中，這兩個程序會各被呼叫一次，流程如下：

在程式的第一次執行期間：
- 呼叫 Alicia 並傳入原始排列 $P$。
- 對於 Alicia 回傳的陣列 $Q$：
  - 如果陣列不符合上述限制，你將收到 Output isn't correct 的判決。
  - 否則，陣列 $Q$ 會由評測系統儲存。
在程式的第二次執行期間：
- 呼叫 Beatriz 並傳入陣列 $Q$。

令 $M$ 為你的解決方案在所有測試案例中成功執行魔術時，$K$ 的最小值。

特別地，若 $M = 16$ 則可獲得滿分。

考慮一個 $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