#P1082. 奇偶元素

奇偶元素

题目描述

给定一个数组,从中删除一个元素,如果删除之后这个数组满足:所有奇数位置的数字之和等于所有偶数位置的数字之和,则说明这次删除是成功的。

请输出删除的方案数以及具体的方案(也就是删除哪些位置是成功的)

输入格式

第一行一个正整数 nn,表示一共有 nn 个数字;

第二行 nn 个正整数 aia_i,第 ii 个正整数表示第 ii 个数字的大小 aia_i

输出格式

如果没有一个位置是可以的,则只输出一行一个数 0。

否则输出两行,第一行输出一个正整数表示方案数,第二行从小到大输出可以选择的位置,每两个位置之间有一个空格。

4
1 4 2 3
1
3

样例说明

如果删除第 1 个数字,则数组变成 a=[4,2,3]a=[4,2,3],奇数位置的和为 a1+a3=4+3=7a_1+a_3=4+3=7,偶数位置的和为 a2=2a_2=2727\neq 2,因此不能删除第 11 个数字;

如果删除第 2 个数字,剩下的树即为 a=[1,2,3]a=[1,2,3],奇数位置的和为 a1+a3=1+3=4a_1+a_3=1+3=4,偶数位置的和为 a2=2a_2=2424\neq 2,因此不能删除第 22 个数字;

如果删除第 3 个数字,剩下的树即为 a=[1,4,3]a=[1,4,3],奇数位置的和为 a1+a3=1+3=4a_1+a_3=1+3=4,偶数位置的和为 a2=4a_2=44=44=4,因此删除第 3 个数字为一种可行的方案;

如果删除第 4 个数字,剩下的树即为 a=[1,4,2]a=[1,4,2],奇数位置的和为 a1+a3=1+2=3a_1+a_3=1+2=3,偶数位置的和为 a2=4a_2=4424\neq 2,因此不能删除第 44 个数字。

综上,只有一种方案,就是删除第三个位置,先输出 1 表示一种方案,然后输出 3 表示这个方案删除的位置。

数据范围

本题共 1010 个测试点,每个测试点 1010 分。

对于 10%10\% 的数据,nn 为奇数且 aia_i 均相同;

对于另 10%10\% 的数据,nn 为偶数且 aia_i 均相同;

对于另 30%30\% 的数据,n100n\le 100

对于另 20%20\% 的数据,n103n\le 10^3

对于 100%100\% 的数据,1n2×105,1ai1041\le n\le 2\times 10^5,1\le a_i\le 10^4