P10384 "HOI R1" Hybrid Breeding

$\clubsuit$ Planet X produces a large number of "Dai-horses". Their excellent speed and low energy consumption make them popular across the whole galaxy. But little $\iiint$ is not satisfied with this. He wants to breed even better "Dai-horses" and replace those backward four-legged beasts that still use traditional energy. So, he began to study genetic technology... **This problem only supports C++ submissions.** **Due to technical limitations, please do not submit using C++14 (GCC 9), otherwise you will get Compile Error.** In your code, you must declare the `query` and `cross` functions as follows: ```cpp char query(int k); void cross(int i, int j); ``` The time for calling `query` and `cross` a total of $10^6$ times does not exceed 50 milliseconds. Apart from the time taken by these two functions, the time taken by the interactive library itself does not exceed 100 milliseconds.

#### [Formal Statement] **This is an interactive problem.** Define a **gene** as a character, which is either $\verb!A!$ or $\verb!a!$. Define a **genotype** as a string consisting of two genes, with the uppercase letter before the lowercase letter. That is, one of $\{\verb!aa!,\verb!Aa!,\verb!AA!\}$. The **phenotype** of a genotype is defined as follows: - If the genotype contains $\verb!A!$, then the phenotype is $\verb!A!$. - Otherwise, the phenotype is $\verb!a!$. Two genotypes can **crossbreed** with each other, defined as follows: - Uniformly randomly pick one gene from each of the two genotypes, and combine the two genes into a genotype as the result. Little $\iiint$ has $n$ genotypes, numbered $1,2,\cdots,n$. In each operation, you can give the interactive library two different indices $i,j$. If this is the $k$-th cross, the interactive library will create a new genotype with index $n+k$, whose genotype is the result of crossbreeding $i$ and $j$. You may query the phenotype of the seed with index $x$ any number of times within the time limit. You need to determine the initially given $n$ genotypes within $4.5\times10^5$ crosses. ### Implementation Details **You do not need to, and should not, implement `main()`.** You need to implement the following function: ```cpp vector guess(int n) ``` - $n$ is the number of initial genotypes. - This function should return an array of length exactly $n$, where each element is a string of length 2 representing the genotype you determined. **You must ensure that the uppercase letter comes before the lowercase letter.** - For each test case, this function is called exactly once. This function may call the following functions: ```cpp char query(int k) ``` - $k$ is the index of the genotype you want to query. **You must ensure that this index corresponds to an existing genotype.** - This function returns the phenotype of that genotype. - This function can be called any number of times within the time limit. ```cpp void cross(int i, int j) ``` - $i,j$ are the indices of the two genotypes you want to crossbreed. **You must ensure $i\not=j$ and that both indices correspond to existing genotypes.** - If this is the $k$-th time you call this function, it will create a new genotype with index $n+k$, whose genotype is the result of crossbreeding $i$ and $j$. It is guaranteed that the crossbreeding process is uniformly random. - You can call this function at most $4.5\times10^5$ times. - The judge is non-adaptive. That is, all initial genotypes have already been fixed before `guess` is called.

N/A

N/A

#### [Interactive Example] The following shows one possible interaction process when $n=2$ and the genotypes are $\{\verb!Aa!,\verb!AA!\}$. |Contestant Program|Interactive Library| |:-:|:-:| ||`guess(2)`| |`cross(1,2)`|| ||$\{\verb!Aa!,\verb!AA!,\verb!Aa!\}$| |`cross(1,3)`|| ||$\{\verb!Aa!,\verb!AA!,\verb!Aa!,\verb!aa!\}$| |`query(4)`|| ||$\verb!a!$| |$\{\verb!Aa!,\verb!AA!\}$|| ||`Ok,accepted.`| #### [Constraints] + $2\le n\le 2\times10^4$, and $n$ is even. + In each run, `guess()` will be called exactly once. + The interactive library is guaranteed to be non-adaptive, i.e., all initial genotypes do not change during the interaction. #### [Subtasks] |Subtask|Score|$n\le$|Special Property| |:-:|:-:|:-:|:-:| |$0$|$0$|$2$|None| |$1$|$5$|$2\times10^4$|Guaranteed that there is no $\verb!Aa!$| |$2$|$15$|$500$|None| |$3$|$20$|$2\times10^4$|Guaranteed that there exists at least one $\verb!aa!$| |$4$|$25$|$5\times10^3$|None| |$5$|$35$|$2\times10^4$|None| For all data, $2\le n\le 2\times10^4$, and $n$ is even. Since this problem involves probability and expectation, if you are confident your algorithm is correct, you can try performing more crosses. Translated by ChatGPT 5