Acowdemia II

题目描述

Bessie 正在申请计算机科学研究生院，并在一个享有盛誉的计算机科学实验室获得了面试机会。然而，为了避免冒犯任何人，Bessie 希望确定实验室中现有 $N$ 名成员（$1 \leq N \leq 100$）的相对资历高低。实验室中任意两名成员的资历都不相同，但要确定他们的资历可能很棘手。为此，Bessie 将查看实验室的论文发表情况。

每篇论文都包含一个作者列表，它是实验室所有 $N$ 名成员的一个排列。该列表按每位成员对论文贡献的努力程度从高到低排序。如果多位研究者投入了相同的努力，则按姓名的字母顺序排列。由于资历更高的实验室成员承担更多行政事务，因此资历更高的研究者投入的努力绝不会多于资历更低的研究者。

例如，在一个实验室中有初级学生 Elsie、资历更高的 Mildred 教授，以及资历非常高的 Dean 教授，那么可能有一篇论文的作者顺序为 (Elsie-Mildred-Dean)，如果他们三人的努力程度都不同（即 Elsie 比 Mildred 更努力，Mildred 比 Dean 更努力）。不过，如果 Mildred 和 Dean 投入了相同的努力而 Elsie 投入更多努力，那么作者顺序也可能是 (Elsie-Dean-Mildred)。

给定该实验室的 $K$ 篇论文（$1 \leq K \leq 100$），请帮助 Bessie 对实验室中所有研究者对，判断谁的资历更高（如果可以判断的话）。

输入格式

第一行包含两个整数 $K$ 和 $N$。 第二行包含 $N$ 个以空格分隔的字符串，表示实验室成员的姓名。每个姓名由小写字母组成，长度不超过 10。 接下来的 $K$ 行中，每行包含 $N$ 个以空格分隔的字符串，表示一篇论文的作者列表。

输出格式

输出应包含 $N$ 行，每行有 $N$ 个字符。在第 $i$ 行中，对于任意 $j \neq i$： 如果第 $i$ 个成员确定比第 $j$ 个成员资历更高，则第 $j$ 个字符为 $1$； 如果第 $i$ 个成员确定比第 $j$ 个成员资历更低，则第 $j$ 个字符为 $0$； 如果根据给定论文无法判断，则第 $j$ 个字符为 $?$. 第 $i$ 行的第 $i$ 个字符应为 $B$，因为这是 Bessie 最喜欢的字母。

1 3
dean elsie mildred
elsie mildred dean

B11
0B?
0?B

2 3
elsie mildred dean
elsie mildred dean
elsie dean mildred

B00
1B0
11B

提示

在第一个例子中，唯一的一篇论文 (elsie-mildred-dean) 并不能提供足够信息来判断 Elsie 是否比 Mildred 资历更高，或反之。然而，可以推断 Dean 必须比两者都更资深，因此资历顺序 Elsie<Mildred<Dean 与 Mildred<Elsie<Dean 都是可能的。

在第二个例子中，与两篇论文都一致的唯一资历顺序是 Elsie<Mildred<Dean，因为第二篇论文基于上面第一个例子中的信息，并帮助我们推断 Mildred 也比 Elsie 更资深。

题目致谢：Dhruv Rohatgi

标签: USACO|2021|Bronze

来源

USACO|2021|Bronze