#P14066. [PO Final 2022] 分组 / Triangeltal

    ID: 15836 远端评测题 5000ms 1024MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>贪心2022Special Judge排序构造PO(瑞典)

[PO Final 2022] 分组 / Triangeltal

题目描述

在一所班级里有 NN 名学生,现在到了必须进行的演讲环节。大多数学生都非常期待演讲,恨不得立刻轮到自己。但在此之前,需要先把他们分成 3 个小组。随后,组 1 的所有人会向组 2 演讲,组 2 向组 3 演讲,组 3 向组 1 演讲。

让分组变得复杂的是,学生的追求程度不同。每位学生 ii 要求自己至少要在 AiA_i 位听众面前演讲,其中 AiA_i 为正整数。举例而言,如果学生 ii 被分到组 1,那么为了让学生 ii 满意,组 2 必须至少有 AiA_i 名成员。这个要求对三组按循环关系成立:

  • 若学生 ii 在第 1 组,则第 2 组的人数至少为 AiA_i
  • 若学生 ii 在第 2 组,则第 3 组的人数至少为 AiA_i
  • 若学生 ii 在第 3 组,则第 1 组的人数至少为 AiA_i

给定这 NN 个数 AiA_i,你的任务是判断是否存在一种把学生分成三组的方法,使得所有学生都满意;如果存在,请找出一种合法的分组。

输入格式

第一行包含一个整数 NN3N51053 \le N \le 5 \cdot 10^5)。
第二行包含 NN 个整数 AiA_i1AiN1 \le A_i \le N)。

输出格式

如果不存在合法分组,输出仅包含字符串 NO\texttt{NO} 的一行。

如果存在合法分组,先输出一行字符串 YES\texttt{YES}。随后输出一行字符串 SS,它由字符 1、2 和 3 组成。字符串中第 ii 个位置的字符表示学生 ii 被分到了哪一组。如果有多种解,输出任意一种均可。

10
1 3 1 3 3 2 4 1 5 2
YES
3313332121
3
1 2 2
NO

提示

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | 11 | 1414 | A1=A2==ANA_1 = A_2 = \dots = A_N | | 22 | 1616 | N10N \le 10 | | 33 | 1111 | Ai3A_i \le 3 | | 33 | 2323 | N3000N \le 3000 | | 44 | 3636 | 无额外限制 |