字符串
所有输入均从 string.in 读取,所有输出均写入 string.out。
时间限制:1 秒。内存限制:512 MiB。
题目描述
有 n 条按顺序排列的记录,第 i 条记录要求分配一个长度恰好为 li 的二进制字符串。二进制字符串是只由字符 0 和 1 组成的字符串。
你需要先删去恰好一条记录,再为每条保留的记录分配字符串。要求按照记录的原顺序,这些字符串的字典序严格递增;同时,任意一个字符串都不能是另一个字符串的前缀。
规定 0<1。比较两个不同字符串的字典序时,首个不同位置的字符较小者更小;若其中一个字符串是另一个字符串的前缀,则较短者更小。字符串 s 是 t 的前缀,是指 s 恰好由 t 开头的 ∣s∣ 个字符组成。
请输出所有可以删除的记录的原编号,使得删除后存在满足要求的字符串分配方案。每个删除位置独立判断,不同删除位置可以使用不同的分配方案。你不需要输出这些字符串。
输入格式
第一行包含一个正整数 n。
第二行包含 n 个正整数 l1,l2,…,ln,表示每条记录要求的字符串长度。
输出格式
输出一行。首先输出一个整数 k,表示可以删除的记录数量;随后按从小到大的顺序输出这 k 条记录的原编号。
如果不存在可以删除的记录,只输出一个整数 0。
样例
样例 1
输入:
4
2 1 2 2
输出:
2 1 2
删除第 1 条记录后,可以依次分配 0、10、11。
删除第 2 条记录后,可以依次分配 00、01、10。删除第 3 条或第 4 条记录都不存在合法方案。
附加样例
样例 2 见 down/string2.in 与 down/string2.ans,满足测试点 5∼6 的限制。
样例 3 见 down/string3.in 与 down/string3.ans,满足测试点 7∼10 的限制。
样例 4 见 down/string4.in 与 down/string4.ans,满足测试点 11∼12 的限制。
样例 5 见 down/string5.in 与 down/string5.ans,满足测试点 13∼20 的限制。
数据范围
| 测试点编号 |
n≤ |
maxli≤ |
特殊性质 |
| 1∼4 |
8 |
4 |
无 |
| 5∼6 |
2×105 |
60 |
A |
| 7∼10 |
2000 |
无 |
| 11∼12 |
2×105 |
12 |
| 13∼20 |
60 |
对于所有测试点,2≤n≤2×105,1≤li≤60。
特殊性质 A:l1=l2=⋯=ln。