Background

$\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:

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.

Problem Description

[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:

vector<string> 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:

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.

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.

Hint

[Interactive Example]

The following shows one possible interaction process when $n=2$ and the genotypes are $\{\verb!Aa!,\verb!AA!\}$.

[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]

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