CF847F Berland Elections

今天是 Berland 议会选举日，投票正在如火如荼地进行！ 共有 $n$ 名候选人，他们的编号从 $1$ 到 $n$。根据选举结果，得票数排名前 $k$ ($1\leq k\leq n$) 的候选人将进入议会。 投票结束后，将统计每位候选人的得票数，并根据得票数对候选人进行排序。如果出现得票数相同的情况，则按照最后一票投给他们的时间顺序排序。最后一票更早的候选人排名更高。 因此，最终的表格中，候选人首先按照得票数从高到低排序。如果有得票数相同，则再按最后一票的时间更早者排名更高。 得票为零的候选人不可能进入议会。因此，最终进入议会的候选人数可能会少于 $k$ 人。 Berland 有 $m$ 名公民可参与投票。每位公民都必须投给某一位候选人。每位公民只能投给其中 $n$ 名候选人中的一人。选票上没有“反对所有人”的选项，也不允许毁票或弃权。所以 $m$ 位公民都会投票给某一位候选人。 现在已有 $a$ 位公民完成了投票（$1\leq a\leq m$）。选举是公开的，对于每一位已经投票的公民，大家都知道他们投给了哪位候选人。形式上，第 $j$ 位公民投票给了第 $g_j$ 号候选人。已经投票的公民按时间顺序编号，即第 $(j+1)$ 位公民比第 $j$ 位更晚投票。 还剩下 $m-a$ 位公民尚未投票，他们将在选举结束前进行投票，每个人都会投给某一位候选人。 你的任务是，对于每一位候选人，判断其最终可能出现的三种情况中的哪一种： - 该候选人无论剩下的 $m-a$ 位公民如何投票，都必定能进入议会； - 该候选人在所有公民都投完票后有机会进入议会； - 该候选人无论剩下的 $m-a$ 位公民如何投票，都不可能进入议会。

第一行包含四个整数 $n$、$k$、$m$、$a$（$1\leq k\leq n\leq 100$，$1\leq m\leq 100$，$1\leq a\leq m$），分别表示候选人数、议会席位数、Berland 公民数以及已经投票的公民数。 第二行包含 $a$ 个整数 $g_{1},g_{2},...,g_{a}$（$1\leq g_{j}\leq n$），表示第 $j$ 位公民投给了第 $g_j$ 号候选人。已有投票的公民按投票时间顺序编号。

输出一行，由 $n$ 个整数 $r_1, r_2, ..., r_n$ 组成： - 若 $r_i=1$，表示第 $i$ 号候选人无论剩余 $m-a$ 位公民如何投票，都会进入议会； - 若 $r_i=2$，表示第 $i$ 号候选人在剩余 $m-a$ 位公民合理投票情况下，有机会进入议会； - 若 $r_i=3$，表示第 $i$ 号候选人无论剩余 $m-a$ 位公民如何投票，都不可能进入议会。

由 ChatGPT 5 翻译