CF1131D.Gourmet choice
普及+/提高
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Mr. Apple, a gourmet, works as editor-in-chief of a gastronomic periodical. He travels around the world, tasting new delights of famous chefs from the most fashionable restaurants. Mr. Apple has his own signature method of review — in each restaurant Mr. Apple orders two sets of dishes on two different days. All the dishes are different, because Mr. Apple doesn't like to eat the same food. For each pair of dishes from different days he remembers exactly which was better, or that they were of the same quality. After this the gourmet evaluates each dish with a positive integer.
Once, during a revision of a restaurant of Celtic medieval cuisine named «Poisson», that serves chestnut soup with fir, warm soda bread, spicy lemon pie and other folk food, Mr. Apple was very pleasantly surprised the gourmet with its variety of menu, and hence ordered too much. Now he's confused about evaluating dishes.
The gourmet tasted a set of n dishes on the first day and a set of m dishes on the second day. He made a table a of size n×m, in which he described his impressions. If, according to the expert, dish i from the first set was better than dish j from the second set, then aij is equal to ">", in the opposite case aij is equal to "<". Dishes also may be equally good, in this case aij is "=".
Now Mr. Apple wants you to help him to evaluate every dish. Since Mr. Apple is very strict, he will evaluate the dishes so that the maximal number used is as small as possible. But Mr. Apple also is very fair, so he never evaluates the dishes so that it goes against his feelings. In other words, if aij is "<", then the number assigned to dish i from the first set should be less than the number of dish j from the second set, if aij is ">", then it should be greater, and finally if aij is "=", then the numbers should be the same.
Help Mr. Apple to evaluate each dish from both sets so that it is consistent with his feelings, or determine that this is impossible.
苹果先生是一位美食家,担任一份美食杂志的主编。他周游世界,品尝来自最时尚餐厅的名厨们制作的新颖美味。苹果先生有自己独特的点评方式——在每家餐厅,他都会在两天内各点一套菜品。所有菜品均不相同,因为苹果先生不喜欢吃重复的食物。对于来自不同日期的每一对菜品,他都能准确记住哪一个更好,或者两者品质相当。之后,这位美食家会为每道菜品赋予一个正整数作为评分。
有一次,在对一家名为「Poisson」的凯尔特中世纪风味餐厅进行评测时,该餐厅供应栗子云杉汤、温热苏打面包、辛辣柠檬派及其他民间风味菜肴,苹果先生被其丰富的菜单深深打动,因而点得过多。如今,他对自己该如何为这些菜品评分感到困惑。
这位美食家第一天品尝了 n 道菜品,第二天品尝了 m 道菜品。他制作了一张大小为 n×m 的表格 a 来记录自己的感受:若根据他的专业判断,第一天的第 i 道菜品优于第二天的第 j 道菜品,则 aij 为 ">";反之,若第一天的第 i 道菜品不如第二天的第 j 道菜品,则 aij 为 "<";若两者品质相当,则 aij 为 "="。
现在,苹果先生希望你帮助他为每道菜品赋值。由于苹果先生极为严格,他将采用尽可能小的最大数值来为菜品评分。但苹果先生也极为公正,因此绝不会给出违背自身感受的评分。换言之:若 aij 为 "<",则第一天第 i 道菜品的评分必须小于第二天第 j 道菜品的评分;若 aij 为 ">",则前者评分必须大于后者;若 aij 为 "=",则两者评分必须相等。
请帮助苹果先生为两套菜品中的每一道都赋予一个评分,使其完全符合他的感受;若不可能实现,请予以判定。
输入格式
The first line contains integers n and m (1≤n,m≤1000) — the number of dishes in both days.
Each of the next n lines contains a string of m symbols. The j-th symbol on i-th line is aij. All strings consist only of "<", ">" and "=".
第一行包含两个整数 n 和 m(1≤n,m≤1000)——分别表示两天中菜肴的数量。
接下来的 n 行,每行包含一个长度为 m 的字符串。第 i 行的第 j 个字符为 aij。所有字符串仅由字符 "<"、">" 和 "=" 组成。
输出格式
The first line of output should contain "Yes", if it's possible to do a correct evaluation for all the dishes, or "No" otherwise.
If case an answer exist, on the second line print n integers — evaluations of dishes from the first set, and on the third line print m integers — evaluations of dishes from the second set.
输出的第一行应包含“Yes”,如果可以对所有菜品进行正确的评分;否则为“No”。
如果存在解,则在第二行输出 n 个整数——即第一组菜品的评分;在第三行输出 m 个整数——即第二组菜品的评分。
输入输出样例
输入#1
3 4 >>>> >>>> >>>>
输出#1
Yes 2 2 2 1 1 1 1
输入#2
3 3 >>> <<< >>>
输出#2
Yes 3 1 3 2 2 2
输入#3
3 2 == =< ==
输出#3
No
说明/提示
In the first sample, all dishes of the first day are better than dishes of the second day. So, the highest score will be 2, for all dishes of the first day.
In the third sample, the table is contradictory — there is no possible evaluation of the dishes that satisfies it.
在第一个样例中,第一天的所有菜肴都优于第二天的所有菜肴。因此,所有第一天的菜肴得分均为 2。
在第三个样例中,该表格是矛盾的——不存在满足该表格的菜肴评分方案。
输入解题思路,AI测评打分。不知道怎么写?