QOJ.ac

QOJ

时间限制: 2 s 内存限制: 512 MB 总分: 100 难度: [显示]

#5140. 冻结的记分牌

统计

在两千年前的秦朝,曾举办过一场 ICPC 竞赛。比赛共有 $m$ 道题目和 $n$ 支队伍。历史记录中仅记载了每支队伍解出的题目数量以及他们使用的总时间。这些被称为队伍的最终结果。我们不知道他们具体解出了哪些题目,也不知道他们的提交时间。

最近,我们似乎有了一个发现。我们找到了队伍的冻结记分牌。从一支队伍的冻结记分牌中,我们可以知道他们在整个比赛期间的提交情况,但不知道最后一小时内提交的判决结果。此外,有人发现对于某些队伍,他们的冻结记分牌可能与历史记录中的最终结果相矛盾。

给定各队的最终结果和冻结记分牌,请为每支队伍构建一个既符合其最终结果又符合其冻结记分牌的最终记分牌。

根据比赛期间的提交情况,我们可以按如下方式计算最终记分牌和最终结果:

对于固定的队伍 $i$,其最终记分牌是一个包含 $m$ 个元素的数组,其中第 $j$ 个元素显示了队伍 $i$ 在题目 $j$ 上的相关信息。

  • 如果队伍 $i$ 没有提交过题目 $j$,则该单元格应为一个字符 “.”(不含引号)。
  • 如果队伍 $i$ 对题目 $j$ 提交了 $x$ 次且没有一次通过,则该单元格应包含 $- x$。
  • 否则,考虑队伍 $i$ 对题目 $j$ 的所有提交。每次提交都有一个提交时间。假设最早的一次通过提交是第 $x$ 次。那么该单元格应包含 $+ x/y$,其中 $y$ ($0 \le y \le 299$) 是第 $x$ 次提交的提交时间。$y$ 是表示提交时间(以分钟为单位)的整数。

注意,在最终记分牌中,我们不关心第一次通过之后的提交。两名或多名选手的提交可能发生在同一分钟。

队伍的最终结果由其最终记分牌计算得出。对于每支队伍,我们可以计算其解出的题目数量。该数量等于队伍最终记分牌中 “+” 的数量。

我们还可以计算其总时间。如果队伍 $i$ 在第 $y$ 分钟解出了题目 $j$,且之前有 $x-1$ 次未通过的提交(换句话说,最终记分牌中第 $i$ 行第 $j$ 个单元格为 $+ x/y$),则题目 $j$ 为队伍 $i$ 贡献了 $20(x - 1) + y$ 的时间。如果队伍 $i$ 没有解出题目 $j$,则无论队伍 $i$ 是否提交过题目 $j$,题目 $j$ 对队伍 $i$ 的贡献均为 0。队伍 $i$ 的总时间是每道题目贡献之和。

冻结记分牌的规则将在输入部分介绍。我们将区分最后一小时内的提交和其他提交。如果提交时间在 240 到 299 分钟之间,则该提交属于最后一小时。

输入格式

第一行包含两个整数 $n, m$ ($1 \le n \le 1000, 1 \le m \le 13$),分别表示参赛队伍数量和题目数量。

接下来有 $n$ 个数据块,描述每支队伍的最终结果和冻结记分牌。

第 $i$ 个数据块代表队伍 $i$。在该数据块中,第一行包含两个整数 $a_i, b_i$ ($0 \le a_i \le m, 0 \le b_i \le 10^5$),分别表示队伍 $i$ 在整个比赛期间解出的题目数量和解出 $a_i$ 道题目的总时间。这两个数字代表了比赛的最终结果。接下来的 $m$ 行描述了队伍 $i$ 在冻结记分牌中的状态。对于每个 $1 \le j \le m$:

  • 如果第 $j$ 行是 $+ x/y$ ($1 \le x \le 100, 0 \le y \le 239$),表示队伍 $i$ 在第 $y$ 分钟解出了题目 $j$,且通过的提交是他们的第 $x$ 次提交。
  • 如果第 $j$ 行是 $? x y$ ($1 \le x \le y \le 100$),表示队伍 $i$ 在前四个小时内没有解出题目 $j$。队伍 $i$ 对题目 $j$ 总共提交了 $y$ 次,其中有 $x$ 次提交是在最后一小时内进行的。注意,最后一小时内发生在通过提交之后的提交会计入冻结记分牌,但不会计入最终记分牌。
  • 如果第 $j$ 行是 $- x$,表示队伍 $i$ 在前四个小时内没有解出题目 $j$。队伍 $i$ 在最后一小时之前对题目 $j$ 提交了 $x$ ($1 \le x \le 100$) 次,且在最后一小时内没有提交题目 $j$。
  • 如果第 $j$ 行是单个字符 “.”(不含引号),表示队伍 $i$ 完全没有提交过题目 $j$。

输出格式

对于每支队伍 $i$,如果其最终结果与冻结记分牌矛盾,则输出一行 No。否则,第一行输出 Yes,随后输出 $m$ 行。第 $j$ 行应包含:

  • $+ x/y$ ($1 \le x \le 100, 0 \le y \le 299$),如果队伍 $i$ 对题目 $j$ 的第 $x$ 次提交通过,且发生在比赛的第 $y$ 分钟。队伍 $i$ 对题目 $j$ 在第 $x$ 次提交之前的所有提交均未通过。请不要在斜杠 “/” 前后输出多余空格。
  • $- x$ ($1 \le x \le 100$),如果队伍 $i$ 对题目 $j$ 提交了 $x$ 次且没有一次通过。
  • $.$,如果队伍 $i$ 完全没有提交过题目 $j$。

请注意,在输入和输出中,每个 $?$, $+$, 和 $-$ 后面总是跟有一个空格。

样例

样例输入 1

1 13
7 951
+ 1/6
? 3 4
+ 4/183
- 2
+ 3/217
.
.
.
+ 2/29
+ 1/91
.
+ 1/22
.

样例输出 1

Yes
+ 1/6
+ 2/263
+ 4/183
- 2
+ 3/217
.
.
.
+ 2/29
+ 1/91
.
+ 1/22
.

样例输入 2

6 2
1 100
.
? 3 4
2 100
+ 1/1
+ 1/2
0 0
- 5
- 6
2 480
? 100 100
? 100 100
2 480
? 99 100
? 100 100
1 2000
? 100 100
? 100 100

样例输出 2

No
No
Yes
- 5
- 6
Yes
+ 1/240
+ 1/240
No
Yes
+ 87/280
- 100

说明

以下是第一个样例中冻结记分牌的示例:

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.