CF1634E Fair Share

题目描述

给定 $m$ 个数组,第 $i$ 个数组包含 $n_i$ 个整数 $a_{i,1},a_{i,2},\dots,a_{i,n_i}$,保证 $2\mid n_i$。另外还有两个初始为空的可重集 $L, R$,你需要对于 $i = 1,2,\dots,m$ 依次执行如下操作: - 将第 $i$ 个数组中的所有数当中选出 $\frac{n_i}{2}$ 个数放入 $L$ 中,另一半则放入 $R$ 中。 你需要保证在每一个数组内的所有数都放入两个可重集之后,$L = R$ 成立。请给出一种放置 $m$ 个数组中的数的方案,或者判断不存在这样一种方案。

输入格式

第一行输入一个正整数 $m$($1\leq m_i\leq 10^5$),表示数组的数量; 接下来 $2 \cdot m$ 行描述数组,对于每个数组,第一行输入一个正整数 $n_i$($2\leq n_i,2 \mid n_i,\sum n_i\leq 2\times 10^5$),表示数组的长度,第二行输入 $n_i$ 个正整数 $a_1,a_2,\dots,a_n$($1\leq a_i\leq 10^9$),表示数组的元素。

输出格式

如果存在答案,第一行输出 `YES`,接下来 $m$ 行,对于第 $i$ 行,第 $i$ 个数组的每个元素如果放在 $L$ 中,就输出 `L`,否则输出 `R`; 如果不存在答案,输出单独一行 `NO`。

说明/提示

对于第 $1$ 个数组,我们将第 $1$ 个数放在 $R$,第 $2$ 个数放在 $L$,这样会使 $L=\{2\},R=\{1\}$; 对于第 $2$ 个数组,我们将第 $1,3$ 个数放在 $L$,其他数放在 $R$,这样会使 $L=\{1,2,3\},R=\{1,2,3\}$; 对于第 $3$ 个数组,我们将第 $2,3,6$ 个数放在 $L$,其他数放在 $R$,最终 $L=R=\{1,1,2,2,3,3\}$;