← 返回题目列表

Codeforces · 732/E

E. 插座

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

ICM ACPC世界总决赛来了!遗憾的是,赛事组织者忙于准备工作,完全忽略了一个重要的技术点——为所有参赛者工作站组织供电。

参与者有 n 台计算机,其中第 i 台的幂等于正整数 pi。同时有 m 个可用插座,其中第 j 个插座的功率等于正整数 sj。当且仅当它们的功率相同时,才可以将第 i 个计算机连接到第 j 个插座:pi = sj。一个插座上最多只能连接一台计算机。因此,如果所有计算机和插座的电源是不同的,则没有计算机可以连接到任何插座。

为了解决这个问题,Puch Williams 教授紧急订购了一车适配器——功率分配器。每个适配器都有一个插头和一个插座,它们之间有一个分压器。将适配器插入功率为 x 的插座后,适配器插座上的功率等于 $$\left\lfloor \frac{x}{2} \right\rfloor$$,这意味着它等于插座功率除以 2 并向上舍入,例如 $$\left[\frac{10}{2}\right]=5$$ 和 $$\left\lfloor \frac{15}{2} \right\rfloor = 8$$。

每个适配器只能使用一次。可以将多个适配器连接成一条链,将第一个适配器插入插座。例如,如果将两个适配器依次插入电源为10的插座,则可以将一台电源为3的计算机连接到该插座。

组织者应安装适配器,以便可以同时为最大数量的计算机c供电。如果有多种可能的连接配置,他们希望找到一种使用最少数量的适配器 u 连接 c 台计算机的配置。

帮助组织者计算连接计算机的最大数量 c 以及为此所需的适配器的最小数量 u。

适配器车里有足够的适配器来完成任务。保证可以连接至少一台计算机。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200 000) — 计算机数量和套接字数量。

第二行包含 n 个整数 p1, p2, ..., pn (1 ≤ pi ≤ 109) - 计算机的幂。

第三行包含 m 个整数 s1, s2, ..., sm (1 ≤ si ≤ 109) — 插座的功率。

输出

第一行打印两个数字c和u——可以同时通电的最大计算机数量和连接c计算机所需的最小适配器数量。

在第二行中打印 m 个整数 a1, a2, ..., am (0 ≤ ai ≤ 109),其中 ai 等于组织者需要插入第 i 个插座的适配器数量。所有ai的总和应该等于u。

在第三行中打印 n 个整数 b1, b2, ..., bn (0 ≤ bi ≤ m),其中第 bj 等于第 j 台计算机应连接的套接字号。 bj = 0 表示第 j 台计算机不应连接到任何套接字。所有不同于 0 的 bj 应该是不同的。第j台计算机插入abj适配器后,其功率应等于插座bj的功率。非零 bj 的数量应等于 c。

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

示例

输入 #1

2 2
1 1
2 2

输出 #1

2 2
1 1
1 2

输入 #2

2 1
2 100
99

输出 #2

1 6
6
1 0