AT_abc134_d.[ABC134D] Preparing Boxes
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 N 个空箱子横向排列成一排。从左到右第 i(1≤i≤N)个箱子上写着整数 i。
すぬけさん可以选择在每个箱子里放一个球,或者什么都不放。
现在,定义满足以下条件的放球方式为“好”的放球方式:
- 对于任意 1 到 N 的整数 i,所有编号是 i 的倍数的箱子中球的总数对 2 取余的结果等于 ai。
请判断是否存在“好”的放球方式。如果存在,请给出一种方案。
输入格式
输入通过标准输入给出,格式如下:
N a1 a2 ... aN
输出格式
如果不存在“好”的放球方式,输出 -1。
如果存在,请输出一种这样的放法,格式如下:
M b1 b2 ... bM
其中 M 表示放了球的箱子的数量,b1,b2,...,bM 表示这些箱子上写的整数,顺序任意。
输入输出样例
输入#1
3 1 0 0
输出#1
1 1
输入#2
5 0 0 0 0 0
输出#2
0
说明/提示
限制
- 所有输入均为整数。
- 1≤N≤2×105
- ai 只可能是 0 或 1。
样例解释 1
考虑只在写着 1 的箱子里放球的情况。
- 写着 1 的倍数的箱子有写着 1、2、3 的箱子共 3 个。这些箱子里球的总数为 1。
- 写着 2 的倍数的箱子只有写着 2 的箱子,共 1 个。这些箱子里球的总数为 0。
- 写着 3 的倍数的箱子只有写着 3 的箱子,共 1 个。这些箱子里球的总数为 0。
因此,只在写着 1 的箱子里放球是一种满足条件的“好”的放球方式。
样例解释 2
有时什么球都不放也是一种“好”的放法。