B. 字符串

    传统题 文件IO:string 1000ms 512MiB

字符串

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

字符串

所有输入均从 string.in 读取,所有输出均写入 string.out。

时间限制:11 秒。内存限制:512512 MiB。

题目描述

有 nn 条按顺序排列的记录,第 ii 条记录要求分配一个长度恰好为 lil_i 的二进制字符串。二进制字符串是只由字符 0\texttt{0} 和 1\texttt{1} 组成的字符串。

你需要先删去恰好一条记录,再为每条保留的记录分配字符串。要求按照记录的原顺序,这些字符串的字典序严格递增;同时,任意一个字符串都不能是另一个字符串的前缀。

规定 0<1\texttt{0}<\texttt{1}。比较两个不同字符串的字典序时,首个不同位置的字符较小者更小;若其中一个字符串是另一个字符串的前缀,则较短者更小。字符串 ss 是 tt 的前缀,是指 ss 恰好由 tt 开头的 ∣s∣|s| 个字符组成。

请输出所有可以删除的记录的原编号,使得删除后存在满足要求的字符串分配方案。每个删除位置独立判断,不同删除位置可以使用不同的分配方案。你不需要输出这些字符串。

输入格式

第一行包含一个正整数 nn。

第二行包含 nn 个正整数 l1,l2,…,lnl_1,l_2,\ldots,l_n,表示每条记录要求的字符串长度。

输出格式

输出一行。首先输出一个整数 kk,表示可以删除的记录数量;随后按从小到大的顺序输出这 kk 条记录的原编号。

如果不存在可以删除的记录,只输出一个整数 00。

样例

样例 1

输入:

4
2 1 2 2

输出:

2 1 2

删除第 11 条记录后,可以依次分配 0\texttt{0}、10\texttt{10}、11\texttt{11}。

删除第 22 条记录后,可以依次分配 00\texttt{00}、01\texttt{01}、10\texttt{10}。删除第 33 条或第 44 条记录都不存在合法方案。

附加样例

样例 2 见 down/string2.in\texttt{down/string2.in} 与 down/string2.ans\texttt{down/string2.ans},满足测试点 5∼65\sim6 的限制。

样例 3 见 down/string3.in\texttt{down/string3.in} 与 down/string3.ans\texttt{down/string3.ans},满足测试点 7∼107\sim10 的限制。

样例 4 见 down/string4.in\texttt{down/string4.in} 与 down/string4.ans\texttt{down/string4.ans},满足测试点 11∼1211\sim12 的限制。

样例 5 见 down/string5.in\texttt{down/string5.in} 与 down/string5.ans\texttt{down/string5.ans},满足测试点 13∼2013\sim20 的限制。

数据范围

测试点编号 n≤n\le max⁡li≤\max l_i\le 特殊性质
1∼41\sim4 88 44 无
5∼65\sim6 2×1052\times10^5 6060 AA
7∼107\sim10 20002000 无
11∼1211\sim12 2×1052\times10^5 1212
13∼2013\sim20 6060

对于所有测试点,2≤n≤2×1052\le n\le2\times10^5,1≤li≤601\le l_i\le60。

特殊性质 AA:l1=l2=⋯=lnl_1=l_2=\cdots=l_n。

CSP-S公益营第一套

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-10-18 14:30
结束于
2026-10-18 18:45
持续时间
4.3 小时
主持人
参赛人数
141