[ROI 2018] Addition without carry

ID: 10315

远端评测题

2000ms

512MiB

显示难度NOI/NOI+/CTS

上传者:

标签>

2018

ROI（俄罗斯）

背景

对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\mathtt{OR}$ 和，那么我们称之为「美丽的集合」。

给出 $a_1\ldots a_n$ , 存在一个由数列 $b_1\ldots b_n$ 组成的「美丽的集合」，且满足：

$\forall i=1\ldots n$ ， $b_i\geq a_i$ , 且 $\sum b_i$ 最小。

试求出新数列的 $\sum b_i$ 。

为了简便起见，我们给出的 $a_i$ 均为二进制形式，你的答案也应是二进制形式。

第一行一个整数 $n$ 。

接下来 $n$ 行，一行一个二进制数 $a_i$ 。

输出得出的二进制的 $\sum b_i$ 。

2
10
10

2
10100
1001

对于所有的数据， $1 \leq n \leq 3 \times 10^5$ 。

（在二进制下） $a_i$ 的位数不超过 $3 \times 10^5$ ，并且所有 $a_i$ 的位数之和不超过 $3\times 10^5$ 。

子任务依赖仅供参考，洛谷评测时无子任务依赖。

子任务	分值	$n$	$\max L$	必须通过的子任务
1	4	$n=2$	$\max L \le 10$
2	2		$\max L \le 20$	1
3			$\max L \le 100$	1,2
4			$\max L \le 1000$	1--3
5			$\max L \le 300\,000$	1--4
6	4	$n \le 100$	$\max L \le 100$	保证 $a_i$ 是 $2$ 的幂
7		$n \le 1000$	$\max L \le 1000$	6，保证 $a_i$ 是 $2$ 的幂
8		$n \le 300\,000$	$\max L \le 300\,000$	6,7，保证 $a_i$ 是 $2$ 的幂
9		$n \le 5$	$\max L \le 5$	U
10		$n \le 5$	$\max L \le 1\,000$	U,1--4,9
11		$n \le 1\,000$	$\max L \le 5$	U,9
12		$n \le 10$	$\max L \le 10$	U,1,9
13		$n \le 50$	$\max L \le 50$	U,1,2,9,12
14	7	$n \le 100$	$\max L \le 100$	U,1--3,6,9,12,13
15	7	$n \le 300$	$\max L \le 300$	U,1--3,6,9,12--14
16	8	$n \le 1000$	$\max L \le 1000$	U,1--4,6,7,9--15
17	8	$n \le 3000$	$\max L \le 3000$	U,1--4,6,7,9--16
18	6	$n \le 10\,000$	$\max L \le 10\,000$	U,1--4,6,7,9--17
19	7	$n \le 30\,000$	$\max L \le 30\,000$	U,1--4,6,7,9--18
20	7	$n \le 100\,000$	$\max L \le 100\,000$	U,1--4,6,7,9--19
21	6	$n \le 300\,000$	$\max L \le 300\,000$	U,1--20