P6891 [JOISC 2020] Building Decoration 4

JOISC2020 Day 1 T1.

Given two sequences $A, B$ of length $2n$, construct a sequence $C$ of length $2n$ that satisfies the following conditions: - For $1 \leq i \leq 2n$, $C_i$ can only be chosen from $A_i$ and $B_i$. - The number of times $C_i$ is chosen from $A_i$ and the number of times it is chosen from $B_i$ are both exactly $n$. - $C$ is a non-decreasing sequence. If there are multiple valid sequences $C$, you only need to output one.

The first line contains a positive integer $n$. The second line contains $2n$ numbers, where the $i$-th number is $A_i$. The third line contains $2n$ numbers, where the $i$-th number is $B_i$.

If there is no solution, output $-1$. Otherwise, output a string $s$ in the following way: For $1 \leq i \leq 2n$, if $C_i$ is chosen from $A_i$, then $s_i=\texttt{A}$; otherwise, $s_i=\texttt{B}$.

#### Sample 1 Explanation The constructed $C=[2,5,6,9,12,14]$. You can check for yourself that this satisfies the conditions. #### Sample 2 Explanation There are also $5$ other solutions: $\texttt{AABB}, \texttt{ABAB}, \texttt{BABA}, \texttt{BAAB}, \texttt{ABBA}$. Any one of them is acceptable. #### Sample 3 Explanation There is no solution that satisfies the conditions. #### Subtasks | Subtask | Special Property | Score | | :----------: | :----------: | :----------: | | $1$ | $1 \leq n \leq 2\times 10^3$ | $11$ | | $2$ | None | $89$ | #### Constraints For $100\%$ of the testdata, $1 \leq n \leq 5\times 10^5$, $1 \leq A_i, B_i \leq 10^9$. Translated by ChatGPT 5