#P18784. [TOI22] 犀鸟的合唱
[TOI22] 犀鸟的合唱
犀鸟的合唱
两只犀鸟要合唱一首包含 个音符的歌曲。音符按顺序编号为 ,第 个音符的音高为 。
每个音符必须恰好交给其中一只鸟演唱。两只鸟各自演唱的音符都保持歌曲中的原有顺序。
如果一只鸟依次演唱的音高为 ,它的疲劳值为
演唱零个或一个音符的鸟,疲劳值为 。
请给出一种分配方案,使两只鸟的疲劳值之和最小。存在多个最优方案时,输出任意一个即可。
输入格式
第一行一个整数 。
第二行 个整数 。
输出格式
输出 个整数 ,其中每个整数为 或 ,表示对应音符交给哪只鸟演唱。
不需要输出最小疲劳值。
数据范围
- 。
- 。
时间限制:1 秒。内存限制:512 MB。
子任务
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 7 | |
| 2 | 11 | |
| 3 | 16 | |
| 4 | 18 | 数组中不同音高的数量不超过 |
| 5 | 25 | |
| 6 | 23 | 无附加限制 |
样例
5
1 5 6 3 2
1 0 0 1 1
样例说明
第一只鸟演唱音高 ,疲劳值为 ;第二只鸟演唱音高 ,疲劳值为 。总疲劳值为 ,为最优值。
将两只鸟的编号互换,得到 0 1 1 0 0,也是合法的最优方案。