← 返回题目列表

Codeforces · 1138/B

B. 马戏团

中文机器翻译题面 查看原题

波利卡普是马戏团的团长。剧团中有$$$n$$$——偶数——艺术家。已知第$$$i$$$艺术家是否可以作为小丑表演(如果是,则$$$c_i = 1$$$,否则$$$c_i = 0$$$),以及他们是否可以作为杂技演员表演(如果是,则$$$a_i = 1$$$,否则$$$a_i = 0$$$)。

将艺术家分成两场表演,方式如下:

- 每个艺术家只进行一场表演,
- 两次表演中的艺术家数量相等(即等于 $$$\frac{n}{2}$$$),
- 第一场演出中可以扮演小丑的艺术家人数与第二场演出中可以扮演杂技演员的艺术家人数相同。

输入

第一行包含一个整数 $$$n$$$($$$2 \le n \le 5\,000$$$,$$$n$$$ 为偶数)——剧团中艺术家的数量。

第二行包含 $$$n$$$ 数字 $$$c_1 c_2 \ldots c_n$$$,如果第 $$$i$$$ 位艺术家可以扮演小丑,则第 $$$i$$$ 等于 $$$1$$$,否则等于 $$$0$$$。

第三行包含 $$$n$$$ 位数字 $$$a_1 a_2 \ldots a_n$$$,如果第 $$$i$$$ 位艺术家可以作为杂技演员表演,则第 $$$i$$$ 等于 $$$1$$$,否则为 $$$0$$$。

输出

打印 $$$\frac{n}{2}$$$ 不同的整数 - 应在第一次表演中演奏的艺术家的索引。

如果有多个答案,请打印其中一个。

如果没有解决方案,则打印单个整数 $$$-1$$$。

示例

输入 #1

4
0011
0101

输出 #1

1 4

输入 #2

6
000000
111111

输出 #2

-1

输入 #3

4
0011
1100

输出 #3

4 3

输入#4

8
00100101
01111100

输出#4

1 2 3 6

注意

在第一个示例中,两次表演的可能划分如下:在第一个表演中,$$$1$$$ 和 $$$4$$$ 应该参加。那么第一场表演中可以扮演小丑的艺术家人数就等于$$$1$$$。而第二场演出中能够表演杂技的艺术家人数也是$$$1$$$。

在第二个示例中,无法进行除法。

在第三个例子中,可能的划分之一如下:在第一表演艺术家中$$$3$$$和$$$4$$$应该参加。然后在第一场表演中有 $$$2$$$ 艺术家可以扮演小丑。而第二场演出中能够表演杂技的艺术家人数也是$$$2$$$。