QOJ.ac

QOJ

时间限制: 2 s 内存限制: 512 MB 总分: 100

#2881. 多线程程序

统计

Maurice 正在他的旧机器上调试一个多线程程序。该程序有多个线程,它们操作一组共享变量。每个线程按照预定义的程序顺序执行其自身的赋值序列。每个赋值操作将其中一个变量设置为一个整数值。

当程序运行时,来自不同线程的赋值操作可以以任何顺序执行。唯一的保证是每个线程都按照程序顺序执行其所有的赋值操作。

例如,假设程序有三个线程,它们的序列中分别有 2、2 和 1 个赋值操作。那么一种合法的程序执行顺序如下: 线程 1 执行其序列中的第一个赋值; 线程 2 执行其序列中的第一个赋值; 线程 2 执行其序列中的第二个赋值; 线程 1 执行其序列中的第二个赋值; * 线程 3 执行其序列中的唯一一个赋值。

这种执行过程可以用 1, 2, 2, 1, 3 来描述,其中数字指定了按顺序执行每个赋值的线程。注意,许多其他合法的执行顺序也是可能的。

Maurice 怀疑他的机器坏了,工作不正常。他运行了他的程序,并记录了所有变量在结束时的值。

请找到一个执行程序的方式,使得它完成所有赋值并导致记录的变量值,或者报告机器确实坏了,不存在这样的执行方式。

输入格式

第一行包含一个整数 $t$ — 线程数量 ($1 \le t \le 100$)。线程编号从 1 到 $t$。接下来的行描述了 $t$ 个赋值序列,每个线程一个。

第 $i$ 个描述的第一行包含一个整数 $l_i$ — 第 $i$ 个线程的赋值序列长度 ($1 \le l_i \le 100$)。接下来的 $l_i$ 行包含形式为 “=” 的赋值。赋值按程序顺序排列。变量名由最多 10 个小写英文字母组成,值是不超过 $10^9$ 的正整数。

剩余行中的第一行包含一个整数 $k$ — 变量数量 ($1 \le k \le 10\,000$)。接下来的 $k$ 行包含变量名及其记录的值,该值是不超过 $10^9$ 的正整数。程序中使用的每个变量都恰好列出一次,且每个列出的变量至少被使用过一次赋值。

输出格式

如果存在产生记录值的执行方式,则输出 “Yes”,否则输出 “No”。

如果存在这样的执行方式,输出一行包含 $s = l_1 + l_2 + \dots + l_t$ 个整数 $c_1, c_2, \dots, c_s$,描述这样一种执行方式 ($1 \le c_i \le t$)。这指定了第一个赋值由线程 $c_1$ 执行,第二个由线程 $c_2$ 执行,依此类推。每个线程按照程序顺序执行其赋值。在第 $s$ 个赋值之后,每个变量必须具有记录的值。第 $i$ 个线程必须在描述中恰好出现 $l_i$ 次。

样例

输入 1

2
2
a=1
b=2
2
b=1
a=2
2
a 1
b 1

输出 1

No

输入 2

3
5
start=1
counter=1111
counter=10
counter=3333
finish=1
4
start=2
counter=20
counter=10
finish=2
3
start=3
qwerty=787788
finish=3
4
counter 10
start 1
finish 1
qwerty 787788

输出 2

Yes
2 3 3 2 1 1 3 1 1 2 2 1

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.