题目描述

Real-time software in the Mars Pathfinder spacecraft suffered from an issue known as priority inversion. One technique to address this issue is to use the Priority Ceiling Protocol.

In this problem, you will simulate the execution of multiple tasks according to this protocol. The tasks share a collection of resources, each of which can be used by only one task at a time. To ensure this, resources must be locked before use and unlocked after use. Each task is defined by a start time, a unique base priority, and a sequence of instructions. Each task also has a current priority, which may change during execution. Instructions come in three types:

compute – perform a computation for one microsecond

lock $k$ – lock resource $k$ (which takes no processor time)

unlock $k$ – unlock resource $k$ (which takes no processor time)

After locking a resource, a task is said to own the resource until the task unlocks it. A task will unlock only the owned resource it most recently locked, will not lock a resource it already owns, and will complete with no owned resources.

Each resource has a fixed priority ceiling, which is the highest base priority of any task that contains an instruction to lock that resource.

There is a single processor that executes the tasks. When the processor starts, it initializes its clock to zero and then runs an infinite loop with the following steps:

Step 1.

Identify running tasks. A task is running if its start time is less than or equal to the current processor clock and not all of its instructions have been executed.

Step 2.

Determine the current priorities of the running tasks and which of the running tasks are blocked. A running task $T$ is blocked if the next instruction in $T$ is to lock resource $k$ and either resource $k$ is already owned or at least one other task owns a resource $\ell$ whose priority ceiling is greater than or equal to the current priority of $T$. If $T$ is blocked, it is said to be blocked by every task owning such $k$ or $\ell$. The current priority of a task $T$ is the maximum of $T$’s base priority and the current priorities of all tasks that $T$ blocks.

Step 3.

Execute the next instruction of the non-blocked running task (if any) with the highest current priority. If there was no such task or if a compute instruction was executed, increment the processor clock by one microsecond. If a lock or unlock instruction was executed, do not increment the clock.

The Priority Ceiling Protocol defined above has the following properties:

Current priority is defined in terms of current priority and blocking, and blocking is defined in terms of current priority. While this may appear circular, there will always be a unique set of current priorities that satisfy the definitions.

All tasks will eventually complete.

There will never be a tie in step 3.

输入格式

The first line of the input contains two integers $t$ $(1 \leq t \leq 20)$, which is the number of tasks, and $r$ ($1 \leq r \leq 20$), which is the number of resources. This is followed by $t$ lines, where the $i^\text {th}$ of these lines describes task $i$. The description of a task begins with three integers: the task’s start time $s$ ($1 \leq s \leq 10\, 000$), its base priority $b$ ($1 \leq b \leq t$), and an integer $a$ ($1 \leq a \leq 100$). A task description is concluded by a sequence of $a$ strings describing the instructions. Each string is a letter (C or L or U) followed by an integer. The string C$n$ ($1 \leq n \leq 100$) indicates a sequence of $n$ compute instructions. The strings L$k$ and U$k$ ($1 \leq k \leq r$) indicate instructions locking and unlocking resource $k$ respectively.

No two tasks have the same base priority.

输出格式

For each task, display the time it completes execution, in the same order that the tasks are given in the input.

题目大意

你有 $t$ 个进程和 $r$ 个资源，每个进程包含其起始时间与基础优先级（保证两两不同），以及若干条指令。指令有以下三种：

• compute：进行计算，消耗 $1$ 微秒。
• lock k：锁定编号为 $k$ 的资源，不耗时。
• unlock k：解锁编号为 $k$ 的资源，不耗时。

在进程锁定资源后，这个进程就拥有了这个资源直到这个进程将它解锁。保证任意进程只会解锁最近锁定的资源，不会锁定自身拥有的资源，且在进程结束时不会拥有任何资源。

每个资源有一个固定的属性最高优先级，即包含锁定该资源指令的所有进程的最高基础优先级。

有一个处理器处理这些进程。处理器有一个时钟初始为 $0$，然后重复执行下列步骤：

1. 找出所有正在运行的进程。如果进程开始的时间不大于处理器的时钟且该进程的指令未运行完毕，那么称这个进程正在运行。

2. 决定当前所有正在运行的进程的优先级，以及哪些正在运行的进程会被阻塞。进程 $T$ 会被阻塞当且仅当：

   • 进程 $T$ 的下一条指令是锁定资源 $k$。
   • 资源 $k$ 已经被其他进程拥有，或存在另一个进程拥有某个资源 $\ell$，$\ell$ 的最高优先级大于 $T$ 的当前优先级。

   此时我们称进程 $T$ 被所有拥有资源 $k$ 或满足条件的资源 $\ell$ 的进程阻塞。定义 $T$ 的当前优先级为所有阻塞它的进程的当前优先级与它本身的基础优先级的最大值。

3. 执行当前优先级最高且没有被阻塞的进程的下一条指令。如果不存在这样的进程或者执行的指令是 compute，则将时钟加 $1$ 微秒。

你需要求所有进程的结束时间。可以证明所有进程一定会结束。

输入格式：

第一行两个整数 $t,r$ 表示进程和资源个数。

接下来 $t$ 行每行描述一个进程，格式如下：

• 三个整数 $s,b,a$，表示进程起始时间、基础优先级、指令条数。
• 接下来 $a$ 个字符串，每个字符串表示一条指令。字符串形如 Cn 表示连续 $n$ 个 compute 指令（相互独立），Lk 表示锁定资源 $k$，Rk 表示解锁资源 k。

输出格式：

$t$ 行每行一个整数表示进程执行完毕的时间。

数据范围：$1 \le t,r \le 20,s \le 10^4,1 \le b \le t$ 且互不相同，$a \le 100$，Cn 中 $n \le 100$，Lk,Rk 中 $1 \le k \le r$。

Translated by pokefunc (uid=188716)

3 1
50 2 5 C1 L1 C1 U1 C1
1 1 5 C1 L1 C100 U1 C1
70 3 1 C1

106
107
71

3 3
5 3 5 C1 L1 C1 U1 C1
3 2 9 C1 L2 C1 L3 C1 U3 C1 U2 C1
1 1 9 C1 L3 C3 L2 C1 U2 C1 U3 C1

8
15
16

提示

Time limit: 1000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2016