AT_jsc2022_final_c Not a Multiple of 3
题目描述
给定一个只由 $1$ 和 $2$ 组成、长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$。
你需要将 $A$ 分成 $K$ 个连续的子序列。此时,要求每个子序列的元素和都不能被 $3$ 整除。
请判断是否可以进行这样的分割,如果可以,请给出一种满足条件的分割方式。
输入格式
输入按以下格式从标准输入给出:
> $N\ K\ A_1\ A_2\ \cdots\ A_N$
输出格式
如果不存在满足条件的分割方式,输出 `No`。如果存在,请按以下格式输出答案:
> Yes\ $L_1\ L_2\ \cdots\ L_K$
其中,$L_i$ 表示从头算起,第 $i$ 个子序列的长度。更具体地,对于每个 $i$,从 $A$ 的第 $(\sum_{1 \leq j < i}L_j)+1$ 个元素到第 $\sum_{1 \leq j \leq i}L_j$ 个元素为一个连续子序列。$L$ 需要满足 $1 \leq L_i$,以及 $\sum_{1 \leq i \leq K}L_i = N$。
如果有多种方案,输出其中任意一种均视为正确。
说明/提示
### 样例解释 1
例如,将 $A$ 分为 $(1), (2,2,1)$ 两个子序列,可以满足条件。
### 数据范围
- $2 \leq K \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 2$
- 输入的所有数都是整数。
由 ChatGPT 5 翻译