P13868 [SWERC 2020] Restaurants

:::align{center}  ::: 所有人都很高兴能够重新外出并去巴黎的餐厅用餐。然而，在一段时间内，餐厅的座位数量非常有限。我们希望确保餐厅能够接待尽可能多的人，并且顾客能够坐在他们偏好的座位上。 我们有 $N$ 个顾客，编号从 $1$ 到 $N$，以及 $M$ 家餐厅，编号从 $1$ 到 $M$。 每个顾客在餐厅的一个子集中进行预订，并按照偏好顺序给出他们的预订列表。每家餐厅按照某种偏好顺序对收到的预订进行排名——例如，餐厅可能希望先报名的顾客排名更高。每家餐厅 $i$ 还有一个容量 $c_i$，即它可以支持的最大顾客数量。 你的任务是找到一种将部分顾客分配到餐厅的方案，使得满足以下条件： 1. 没有餐厅安排的顾客数量超过其容量。 2. 每个顾客最多在一家餐厅获得一个座位。 3. 不存在一家餐厅 $r$ 和一个顾客 $c$（$c$ 曾向 $r$ 预订），使得： - $c$ 没有被安排座位，或者 $c$ 更偏好 $r$ 而不是他被安排座位的餐厅，并且 - $r$ 还有空位，或者 $r$ 已满但更偏好 $c$ 而不是至少一个被分配给它的顾客。 其他注意事项： - 每个顾客至少进行了一次预订。 - 餐厅只对向其表达预订的顾客进行排名。有可能某家餐厅没有顾客希望向其预订。

第一行包含 $N$ 和 $M$。 接下来的 $M$ 行描述容量，第 $i$ 行包含一个整数 $c_i$，表示餐厅 $i$ 的容量。 接下来 $N$ 行。第 $i$ 行描述顾客 $i$ 的预订列表，按偏好排序：该行包含一个由空格分隔的不同整数列表（在 $1$ 到 $M$ 之间），从最偏好到最不偏好。 接下来 $M$ 行。第 $i$ 行描述餐厅 $i$ 的排序偏好。当没有顾客向餐厅 $i$ 预订时，该行包含数字 $0$，否则包含一个空格分隔的不同整数列表，表示向餐厅 $i$ 预订的顾客列表，按餐厅从最偏好到最不偏好的顺序排列。

输出一个可能的分配方案中获得座位的顾客集合（根据上述规则）。 该集合每行一个顾客，按 $id$ 升序排序。

**数据范围** - $1\leq N \leq 50\,000$ - $1\leq M \leq 10\,000$ - 预订选项的总数最多为 $1\,000\,000$ - $1\leq c_i \leq N$ -------- 由 Qwen3.5-Plus 翻译。