P7211 [JOISC 2020] Chameleon Love

You can write your program in the following code template: ```cpp #include using namespace std; extern "C" int Query(const std::vector &p); extern "C" void Answer(int a, int b); extern "C" void Solve(int N) { } ```

In the JOI Zoo, there are $2\times N$ chameleons. $N$ of them have gender $\rm X$, and the other $N$ have gender $\rm Y$. Each chameleon has its original color, with the following constraints: - The colors of the $\rm X$-gender chameleons are pairwise distinct. - For each $\rm X$-gender chameleon, there exists a $\rm Y$-gender chameleon with the same color. Now each chameleon loves exactly one other chameleon, under the following rules: - Each chameleon only loves a chameleon of the opposite gender. - Each chameleon and the chameleon it loves have different original colors. - There is no chameleon that is loved by two different chameleons. Now you may organize meetings of some chameleons. For each chameleon $s$ in the meeting, let $t$ be the chameleon that $s$ loves. - If $t$ attends the meeting, then the skin color of $s$ becomes the original color of $t$. - Otherwise, the skin color of $s$ remains the original color of $s$. For each meeting you organize, you can count the number of distinct skin colors. By holding at most $2\times 10^4$ meetings, you must determine every pair of chameleons that share the same original color. #### Interaction Details You need to declare two functions before your program: - `int Query(const std::vector &p)`. - `void Answer(int a, int b)`. You need to implement one function: `void Solve(int N)`. - It is called exactly once for each test case. - The meaning of $N$ is as described in the statement. Your program may call the following functions: - `int Query(const std::vector &p)` - You may call this function to organize a chameleon meeting. - $p$ is the list of chameleons attending the meeting. - It returns the number of distinct colors among the attending chameleons. - All numbers in $p$ must be between $1$ and $2\times N$, otherwise it will return `Wrong Answer [1]`. - All numbers in $p$ must be pairwise distinct, otherwise it will return `Wrong Answer [2]`. - You may call this function at most $2\times 10^4$ times; if you exceed this limit, it will return `Wrong Answer [3]`. - `void Answer(int a, int b)` - Call this function to submit a pair of chameleons with the same original color. - Parameters $a$ and $b$ indicate that chameleon $a$ and chameleon $b$ have the same original color. - You must ensure $1\le a,b\le 2\times N$, otherwise it will return `Wrong Answer [4]`. - You must ensure that every chameleon you submit is different from all previously submitted chameleons, otherwise it will return `Wrong Answer [5]`. - If the original colors of $a$ and $b$ are different, it will return `Wrong Answer [6]`. - You must call this function exactly $N$ times, otherwise it will return `Wrong Answer [7]`. If you never violate any of the restrictions during the interaction, then you will be accepted.

The input format of the interactive library is as follows: The first line contains an integer $N$. The second line contains $2\times N$ integers $Y_i$, indicating the gender of each chameleon. If $Y_i=0$, the gender is $\rm X$; if $Y_i=1$, the gender is $\rm Y$. The third line contains $2\times N$ integers $C_i$, where $C_i$ is the color of chameleon $i$. The fourth line contains $2\times N$ integers $L_i$, where $L_i$ indicates that chameleon $i$ likes (loves) chameleon $L_i$. ("稀饭" is a colloquial form of "喜欢", meaning "like".)

The output format of the interactive library is as follows: If you get AC, it outputs one line `Accepted: x`, where $x$ is the number of times you called `int Query(const std::vector &p)`. If you get WA, it outputs one line `Wrong Answer [type]`, where $type$ is the reason for WA. See the interaction details.

#### Sample Explanation The sample calls are as follows: | Library Call | Your Call | Return Value | | :-: | :-: | :-: | | `Solve(4)` | | | | | `Query([])` | $0$ | | | `Query([6, 2])` | $2$ | | | `Query([8, 1, 6])` | $2$ | | | `Query([7, 1, 3, 5, 6, 8])` | $4$ | | | `Query([8, 6, 4, 1, 5])` | $3$ | | | `Answer(6, 4)` | | | | `Answer(7, 8)` | | | | `Answer(2, 1)` | | | | `Answer(3, 5)` | | `sample-02.txt` satisfies the constraints of Subtask 1, and `sample-03.txt` satisfies the constraints of Subtask 4. #### Subtasks and Constraints For $100\%$ of the data, it is guaranteed that $2\le N\le 500$, $0\le Y_i\le 1$, $1\le C_i\le N$, $1\le L_i\le 2\times N$, $Y_i\not=Y_{L_i}$, $C_i\not=C_{L_i}$, and all $L_i$ are pairwise distinct. | Subtask | Special Property | Score | | :-: | :-: | :-: | | $1$ | $L_{L_i}=i (1\le i\le 2\times N)$ | $4$ | | $2$ | $N\le 7$ | $20$ | | $3$ | $N\le 50$ | $20$ | | $4$ | $Y_i=0 (1\le i\le N)$ | $20$ | | $5$ | None | $36$ | #### Notes This problem is translated from [The 19th Japanese Olympiad in Informatics Spring Training Camp](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/index.html) Day 2 [T1 カメレオンの恋](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day2/chameleon-en.pdf). Translated by ChatGPT 5