• 比赛：EJOI 2026 Day 1
• 时间限制：1.5 秒
• 内存限制：1024 MiB
• 题目类型：函数提交题

题目描述

Boris 和 Ihor 找到了一个由 $N$ 个正整数组成的序列

$a_0,a_1,\dots,a_{N-1}$，

并希望把这些数分给两个人。

你事先可以看到完整序列。随后按从左到右的顺序依次处理 $a_0,a_1,\dots,a_{N-1}$。处理每个元素时，必须把它恰好分给 Boris 或 Ihor 中的一人。

两人都要求：自己收到的元素按照收到顺序必须构成一个严格递增序列。

也就是说，每次分给某个人的新元素，都必须严格大于此前最后一次分给他的元素。一个人收到的第一个元素可以是任意值，也允许某个人一个元素都收不到。

对于每个整数 $K=0,1,\dots,N$，你需要独立判断：

是否存在一种划分，使 Boris 恰好收到 $K$ 个元素，并且 Boris 与 Ihor 各自收到的序列都严格递增？

各个 $K$ 之间相互独立，可以使用完全不同的划分方案。

例如 $a=[3,1,4,5,5]$：

• 当 $K=3$ 时，可以把 $3,4,5$ 分给 Boris，把 $1,5$ 分给 Ihor，因此可行；
• 当 $K=0$ 时，所有元素都必须给 Ihor，而序列从 $3,1$ 开始，不严格递增，因此不可行。

该例中仅 $K=2$ 和 $K=3$ 可行。

实现要求

实现：

std::vector<bool> increasing_split(std::vector<int> a);

• a：长度为 $N$ 的输入序列。

返回一个长度恰好为 $N+1$ 的布尔数组。

第 $i$ 个元素为：

• true：存在合法划分，使 Boris 恰好收到 $i$ 个元素；
• false：不存在。

每个测试中该函数恰好调用一次。

数据范围

• $2\le N\le4\cdot10^5$；
• $1\le a_i\le10^9$。

样例 1

Sample grader 输入

5
3 1 4 5 5

Sample grader 输出

001100

说明

• $K=0$：不可行；
• $K=1$：不可行；
• $K=2$：例如把 $a_1=1,a_4=5$ 给 Boris，把 $a_0=3,a_2=4,a_3=5$ 给 Ihor，可行；
• $K=3$：可行；
• $K=4,5$：不可行。

样例 2

Sample grader 输入

4
1 2 3 4

Sample grader 输出

11111

序列本身严格递增，因此无论怎样把元素分给两个人，两人的子序列都仍严格递增。于是 $K=0,1,2,3,4$ 全部可行。

子任务

Sample grader

输入：

• 第一行一个整数 $N$；
• 第二行 $N$ 个整数 $a_0,a_1,\dots,a_{N-1}$。

若返回数组长度不是 $N+1$，Sample grader 会判错。

否则输出一行长度为 $N+1$ 的二进制串：第 $i$ 位为 1 表示 $K=i$ 可行，否则为 0。