← 返回题目列表

Codeforces · 234/H

H. 合并两副牌

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

你面前的桌子上有两副牌,这些牌中有的牌面朝上,有的牌面朝下。您想将它们合并到一副牌中,其中每张牌面朝下。您将分两个阶段进行。

第一阶段是以同一副牌中的牌的相对顺序不改变的方式合并两副牌。也就是说,对于一副牌中任意两张不同的牌i和j,如果牌i位于牌j上方,则合并后牌i也必须位于牌j上方。

第二阶段在第一阶段产生的牌组上进行。在此阶段,执行的操作是车削操作。在一轮中,您可以取出几张最上面的牌,将它们全部翻转,然后放回原处。因此,每张拿走的牌都会被翻转,并且这些牌的顺序也会颠倒。也就是说,回合前位于底部的牌在回合后将位于顶部。

您的任务是确保所有卡片面朝下。求这样一个第一阶段合并牌的顺序和第二阶段翻牌操作的顺序,使所有牌面朝下,且翻牌次数最少。

输入

第一个输入行包含一个整数 n — 第一副牌中的牌数 (1 ≤ n ≤ 105)。

第二个输入行包含 n 个整数,由单个空格分隔 a1, a2, ..., an (0 ≤ ai ≤ 1)。如果第 i 张牌面朝下,则值 ai 等于 0;如果牌面朝上,则值 ai 等于 1。卡片按照从最上面一张到最下面一张的顺序给出。

第三输入行包含整数 m — 第二副牌中的牌数 (1 ≤ m ≤ 105)。

第四输入行包含 m 个整数,用单个空格 b1, b2, ..., bm 分隔(0 ≤ bi ≤ 1)。如果第 i 张牌面朝下,则值 bi 等于 0;如果牌面朝上,则值 bi 等于 1。卡片按照从最上面到最下面的顺序给出。

输出

在第一行中打印 n + m 个空格分隔的整数 - 按顺序排列的卡片编号,它们将位于第一阶段之后。从上到下列出卡片。第一副牌中的牌应按照从上到下的顺序匹配其从 1 到 n 的索引。第二副牌中的牌应与它们的索引相匹配,增加n,即从上到下顺序从n + 1到n + m的数字。

在第二行中打印一个整数 x — 使这副牌中的所有牌面朝下所需的最少回合操作次数。第三行打印x个整数:c1,c2,...,cx(1≤ci≤n+m),每个整数代表从牌堆顶部取出进行回合操作的牌张数。按执行顺序打印操作。

如果有多个最优解,则打印其中任意一个。保证最小运算次数不超过6·105。

示例

输入 #1

3
1 0 1
4
1 1 1 1

输出 #1

1 4 5 6 7 2 3
3
5 6 7

输入 #2

5
1 1 1 1 1
5
0 1 0 1 0

输出 #2

6 1 2 3 4 5 7 8 9 10
4
1 7 8 9