You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Ben has recently learned about binary prefix codes. A binary code is a set of $n$ distinct nonempty code words $s_{i}$ , each consisting of 0s and $1s.$ A code is called a prefix code if for every $i ≠ j$ neither $s_{i}$ is a prefix of $s_{j}$ nor $s_{j}$ is a prefix of $s_{i}$ . A word $x$ is called a prefix of a word $w$ if there exists a possibly empty word $y$ , such that xy $= w$ . For example, $x = 11$ is a prefix of $w = 110$ and $x = 0100$ is a prefix of $w = 0100$ .

Ben found a paper with $n$ lines of binary code in it. However, this paper is pretty old and there are some unreadable characters. Fortunately, each word contains at most one unreadable character.

Ben wants to know whether these $n$ lines could represent a binary prefix code. In other words, can he replace every unreadable character with $0$ or $1$ , so that the code becomes a prefix code?

输入格式

The first line contains integer $n$ -- the number of code words $(1 \le n \le 5 · 10^{5}).$

Next $n$ lines contain nonempty code word records, one per line. Each code word record consists of 0, 1 and ? characters. Every code word record contains at most one ? character that represents unreadable character.

The total length of words does not exceed $5 · 10^{5}$ .

输出格式

Output NO in the first line if the code cannot be a prefix code.

Otherwise, output YES in the first line. Next $n$ lines shall contain code words in the same order as the corresponding code word records in the input.

If there are several prefix codes, that could have been written on the paper, output any one.

题目大意

题目描述

给定 n 个01串，每个字符串至多有一位是未知的，可以填 0 或 1 ，求是否存在一种方案，使得任意一个字符串不是其它任意一个字符串的前缀

输入格式

第一行是一个正整数 n ，代表字符串的数量。 $(1 \leq n \leq 5 \cdot 10^5)$

接下来 n 行每行一个字符串，只可能由 0 、 1 或 ? 组成。 ? 代表未知的位置，每个字符串最多一个。

保证字符串总长度不超过 $5 \cdot 10^5$ 。

输出格式

如果无解，只需要输出 NO 。

如果有解，在第一行输出 YES ，接下来 n 行输出方案。

如果有多组解，只需要输出任意一组。

4
00?
0?00
?1
1?0

YES
000
0100
11
100

3
0100
01?0
01?0

NO

提示

Time limit: 2 s, Memory limit: 2048 MB.