P6891 [JOISC 2020] ビルの飾り付け 4

JOISC2020 Day 1 T1

给定两个长度为 $2n$ 的序列 $A,B$，构造一个长度为 $2n$ 的序列 $C$ 满足以下条件： - 对于 $1\leq i\leq 2n$，$C_i$ 只能从 $A_i$ 和 $B_i$ 中选取 - $C_i$ 从 $A_i$ 中选取的次数和从 $B_i$ 中选取的次数都恰好为 $n$。 - $C$ 为单调不降的序列。 如果满足条件的 $C$ 有多个，只需要输出一个。

第一行一个正整数 $n$。 第二行 $2n$ 个数字，第 $i$ 个为 $A_i$。 第三行 $2n$ 个数字，第 $i$ 个为 $B_i$。

如果无解则输出 $-1$，否则按照以下方式输出一个字符串 $s$： 对于 $1\leq i\leq 2n$，如果 $C_i$ 是从 $A_i$ 选取的则 $s_i=\texttt{A}$，否则 $s_i=\texttt{B}$。

#### 样例 1 解释 构造的 $C=[2,5,6,9,12,14]$，可以自行这是满足条件的方案。 #### 样例 2 解释 另外有 $\texttt{AABB},\texttt{ABAB},\texttt{BABA},\texttt{BAAB},\texttt{ABBA}$ 这 $5$ 组解，输出任何一组均可。 #### 样例 3 解释 没有满足条件的方案。 #### 子任务 | 子任务 | 特殊性质 | 分数 | | :----------: | :----------: | :----------: | | $1$ | $1\leq n\leq 2\times 10^3$ | $11$ | | $2$ | 无 | $89$ | 对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5,1\leq A_i,B_i\leq 10^9$。