[ROI 2018] Addition without carry

Luogu

IDLGP9293

Time2000ms

Memory512MB

DifficultyP7

2018ROI（俄罗斯）

对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\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$ 均为二进制形式，你的答案也应是二进制形式。 ## Input 第一行一个整数 $n$。接下来 $n$ 行，一行一个二进制数 $a_i$。 ## Output 输出得出的二进制的 $\sum b_i$。 [samples] ## Background 译自 [ROI 2018 Day2](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Сложение без переносов ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day2.pdf)([Addition without carry](https://codeforces.com/gym/102154/problem/A))。 ## Note 对于所有的数据，$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 | $n=2$ | $\max L \le 20$ | 1 | | 3 | 2 | $n=2$ | $\max L \le 100$ | 1,2 | | 4 | 2 | $n=2$ | $\max L \le 1000$ | 1--3 | | 5 | 2 | $n=2$ | $\max L \le 300\,000$ | 1--4 | | 6 | 4 | $n \le 100$ | $\max L \le 100$ | | | 7 | 4 | $n \le 1000$ | $\max L \le 1000$ | 6 | | 8 | 4 | $n \le 300\,000$ | $\max L \le 300\,000$ | 6,7 | | 9 | 4 | $n \le 5$ | $\max L \le 5$ | U | | 10 | 4 | $n \le 5$ | $\max L \le 1\,000$ | U,1--4,9 | | 11 | 4 | $n \le 1\,000$ | $\max L \le 5$ | U,9 | | 12 | 4 | $n \le 10$ | $\max L \le 10$ | U,1,9 | | 13 | 4 | $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 |

Samples

Input #1

2
10
10

Output #1

Input #2

2
10100
1001

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2018] Addition without carry",
    "description": {
      "content": "对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\\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_",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9293"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "对于一个只含自然数的集合，如果集合中所有数之和 = 集合中所有数的 $\\mathtt{OR}$ 和，那么我们称之为「美丽的集合」。\n\n给出 $a_1\\ldots a_n$, 存在一个由数列 $b_1\\ldots b_n$ 组成的「美丽的集合」，且满足：\n\n$\\forall i=1\\ldots n$， $b_i\\geq a_i$, 且\n$\\sum b_i$ 最小。\n\n试求出新数列的 $\\sum b_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments