题目
题目背景
西西艾弗岛上，小 F 的团队每天都在忙碌着。他们在解决了进程与接口的通信问题后，开始着手进行进程间资源使用与调度系统的开发。项目开展一段时间后，他们又把你这个资深测试员叫了过来。按照惯例，他们给出了这次资源调度系统的运行模型，并请求你为其编写程序进行模拟。
题目描述
模型中需要考虑的对象有 $n$ 个进程与 $m$ 种资源。进程由 $1,2,\cdots,n$ 依次标号，资源由 $1,2,\cdots,m$ 依次标号。
该系统运行的时间单位称作段。每一段分为“申请”“处理”“释放”三个部分（本题亦称其“段首”“段中”“段末”）。在时间轴上体现如下：
申请部分（段首）专门处理进程对资源的申请行为；在处理部分（段中）每个进程会产生各自的收益；释放部分（段末）专门负责将资源从进程中释放到待使用区。
系统会依次运行第 $1$ 段、第 $2$ 段、……、第 $10^{100}$ 段（视为足够多）。每一段内会依次运行申请部分、处理部分与释放部分。初始所有资源都处于待使用状态。
属性说明
第 $i$ 个进程会从第 $st_i$ 段首开始活动。
第 $i$ 个进程有一个长度为 $k_i$ 的运行任务列表,列表可以由长度为$k_i$的二元组序列表示：
$$
(a_{i,1},t_{i,1}),(a_{i,2},t_{i,2}),\cdots,(a_{i,k_i},t_{i,k_i})
$$
其中：
- $a_{i,j}$ 表示第 $i$ 个进程第 $j$ 次运行任务前会申请的资源编号；
- $t_{i,j}$ 表示第 $i$ 个进程第 $j$ 次运行任务的持续段数。
保证对于同一个 $i$：
$$
a_{i,j_1}\neq a_{i,j_2}\quad(j_1\neq j_2)
$$
单进程行为与收益
一个进程分为：资源申请状态和任务运行状态，刚从某段首开始活动的进程初始为资源申请状态。
- 在某一段首，一个处于资源申请状态的进程会向其当前所需资源发起申请。
- 在某一段中，一个处于任务运行状态的进程会获得收益，收益量等于其在该段段首运行完毕后拥有的资源数量。
在没有任何干扰，资源可以由某 $i$ 号进程任意自由使用的情况下，其理想行为如下：
- $i$ 号进程于第 $st_i$ 段首开始活动，并同时对 $a_{i,1}$ 号资源发起申请。由于没有任何干扰，资源 $a_{i,1}$ 被其占有。同时 $i$ 号进程切换为任务运行状态。
- 接下来的（包括段首申请成功的这一段）$t_{i,1}$ 段里，$i$ 号进程处于任务运行状态。根据定义，每一段中其会获得 $1$ 的收益，该阶段在第 $st_i+t_{i,1} - 1$ 段未结束，同时 $i$ 号进程切换为资源申请状态。
- 在第 $st_i+t_{i,1}$ 段首对 $a_{i,2}$ 号资源发起申请，资源 $a_{i,2}$ 被 $i$ 号进程占有。同时 $i$ 号进程再次切换为任务运行状态。同理，进程继续运行 $t_{i,2}$ 段并获得收益。以此类推，$i$ 号进程可以顺利执行所有 $k_i$ 个任务，过程中不断切换自身状态。
- 最终 $i$ 号进程会在第 $st_i+\sum_{j=1}^{k_i} t_{i,j} - 1$ 段未完成所有运行任务并停止活动。在这一段末，$i$ 号进程会释放所有其使用的资源，也即资源 $a_{i,1}, a_{i,2}, \cdots, a_{i,k_i}$ 均不再被占有，而是变为待使用状态。
根据定义，上述过程 $i$ 号进程从开始活动到结束的理想总收益为 $\sum_{j=1}^{k_i} j \times t_{i,j}$，因为从第 $j$ 次申请成功开始到第 $j+1$ 次申请前，共 $t_{i,j}$ 段，进程 $i$ 在每一段的段中都会获得 $j$ 的收益。
下面图 2 给出了一个 $m=4$, $st_1=2$, $k_1=3$，运行任务列表为 $(1,3), (3,4), (4,3)$ 的 1 号进程的运行示例，你可以借助图 2 理解上述过程。为了不让段首段末的分隔显得杂乱，图中时间轴上每一个小区间表示一个完整的段。
协同运行
然而，任意资源在任意一段都只能被至多一个进程占有。敏锐的你注意到，当多个进程同时活动时，可能在同一段首对同一资源发起申请，就会产生冲突，对此小F对模型进行说明：
考察在第 $s$ 段段首，若多个资源申请状态的进程同时对 $x$ 发起申请：
- 若资源 $x$ 已被占有，则所有进程都会申请失败；
- 否则资源 $x$ 处于待使用状态。设在这些进程中编号最小者的编号为 $i$，则进程 $i$ 申请成功并占有资源 $x$，其它进程均申请失败。
如果一个进程申请成功，则它会自然切换到任务运行状态并继续接下来的任务。
如果一个进程申请失败，它不会切换到任务运行状态，根据定义该段段中不产生收益。它会在第 $s+1$ 段首继续对资源 $x$ 发起申请。
在上例基础上，下图展示了当新增一个 $st_2=3$, $k_2=2$，运行任务列表为 $(2, 6), (4, 2)$ 的 2 号进程后，整个系统的运行情况，你可以借助该图理解上述过程。
死锁优化方案
小 F 指出，如果只是这样设计资源的调配会导致死锁现象的发生，也即两个进程分别占有两种资源，在未释放这两种资源的情况下，又同时对对方占有的另一种资源发起申请，就会导致死循环，永远无法正常运行下去。
为了解决这个问题，小 F 设计了 A、B、C 共 3 种不同的优化方案，每个进程最多采取一种方案。我们将不采取任何方案的进程与采取 A/B/C 三种方案的进程依次称为 X/A/B/C 类进程。前者称为普通进程，后三者称为特殊进程。
每一个 A/B/C 类进程都会拥有一个额外属性 $w_i$，称作忍耐限度。
设某进程 $i$ 刚开始活动或刚运行完上一任务，在第 $s$ 段段首首次对某资源 $x$ 发起申请。如果第 $s$ 段段首至第 $s+w_i-1$ 段段首发起的共 $w_i$ 次申请均失败，则根据类型的不同，进程 $i$ 会有如下行为：
如果进程 $i$ 为 A 类，其会在第 $s+w_i-1$ 段未释放目前占有的所有资源，令其变成待使用状态，自身仍保持资源申请状态持续至资源 $x$，直到申请成功的某一段首切换为当前任务的任务运行状态。
- 值得说明的是，在之后某一段首终于获得资源 $x$ 之后，$i$ 号进程执行任务的收益显然会因为其放弃行为大打折扣，但是其并不会重新申请之前放弃的资源，而是以低收益继续运行自身接下来的任务。如果之后仍然有“卡住”的情况，其仍会按照 A 类进程特性选择放弃。
如果进程 $i$ 为 B 类，其会在第 $s+w_i-1$ 段首申请失败后直接放弃资源 $x$，并将自身切换为任务运行状态，从该段段首直接开始进入对应的 $t_{i*}$ 段运行。显然，该放弃行为也会导致进程 $i$ 最终收益低于其理想收益。
如果进程 $i$ 为 C 类，其会在第 $s+w_i$ 段首直接无视资源 $x$ 当前的归属，直接强行申请成功并将资源 $x$ 占有（同时原来占有资源 $x$ 的进程不再占有资源 $x$），同时切换为任务运行状态运行下去。
设原来占有资源 $x$ 的进程为 $j$（可能为任意进程，例如是上一段首刚刚轮到 $x$ 的另一 C 类进程，或者某因为申请另一资源正卡住的普通进程等等），该抢夺行为除了可能会影响进程 $j$ 的收益以外，不会打断或影响其他任何运行状态。
如果在同一段首对某资源 $x$ 同时有多个 C 类进程的抢夺行为发生，则恰有编号最大的 C 类进程的抢夺行为成功，其它 C 类进程的抢夺行为均失败。抢夺失败的 C 类进程不占有资源 $x$，但也切换为任务运行状态运行下去。
如果资源 $x$ 在同一段首还有其它任何类型进程的申请需求，则响应 C 类进程的抢夺行为，其它申请均失败。
题目的样例中涉及了特殊进程的行为，你可以结合样例解释与相应图片理解上述关键信息。
当所有进程均执行完全部任务并停止活动时，系统运行结束。注意，如果系统没有在第 $10^{100}$ 段末前运行结束，其会强行结束自身运行，所有进程的运行收益不受影响。
现在，小 F 给你提供了 $n$, $m$ 以及 $n$ 个进程的所有信息。请你对上述过程进行模拟并最终输出各个进程的运行收益与运行段数。
输入格式
从标准输入读入数据。
输入的第一行包含两个正整数 $n, m$，表示进程数量与资源种类数。
接下来的 $n$ 行，第 $i$ 行输入第 $i$ 个进程的全部信息。每行首先输入一个 X、A、B、C 中的字符表示进程类型。
如果输入为字符 X 代表进程 $i$ 为普通进程。接下来输入两个正整数 $st_i, k_i$，然后输入 $2k_i$ 个正整数，依次代表 $a_{i,1}, t_{i,1}, a_{i,2}, t_{i,2}, \cdots, a_{i,k_i}, t_{i,k_i}$。
否则代表进程 $i$ 为对应的 A/B/C 类特殊进程。接下来输入三个正整数 $st_i, w_i, k_i$，然后输入 $2k_i$ 个正整数，依次代表 $a_{i,1}, t_{i,1}, a_{i,2}, t_{i,2}, \cdots, a_{i,k_i}, t_{i,k_i}$。
所有同一行的不同信息均由一个空格分隔。
输出格式
输出到标准输出。
请你输出 $n$ 行，每行输出用空格隔开的两个整数。
第 $i$ 行的第一个整数表示系统运行结束后，进程 $i$ 的总运行收益。
第 $i$ 行的第二个整数表示进程 $i$ 从开始活动到停止活动的持续段数。如果进程 $i$ 未正常结束而是因为系统强行终止而结束，请输出 $-1$。
样例 1
输入
1 | 3 5 |
输出
1 | 15 10 |
解释
【样例1解释】
下面列出该样例中涉及的特殊事件：
- 第3～4段首2号进程申请资源1均失败，故其放弃申请1号资源，从第4段中起仅占用资源2运行第二个任务至第5段末。
- 第9～10段首2号进程申请资源3均失败，故其放弃申请3号资源，从第10段中起仅占用资源2，5运行第四个任务至第11段末。
- 第3～5段首，3号进程申请资源1均失败，故于第6段首将1号资源抢夺并占有1号资源运行第一个任务至第7段末；第8段首与1号进程同时申请4号资源因为编号较大失败，持续到第10段首。第11段首3号进程抢夺了刚刚在第10段未被1号进程释放到待使用区的4号资源，并占用资源1，4运行第二个任务至第12段末。
三个进程的运行段数均为 10。
样例 2
见题目目录下的 2.in 与 2.ans。
子任务
- 前 40% 数据：不存在特殊类型进程。
- 另外 40% 数据：不存在 C 类进程。
对于全部数据，保证：
$1\le n\le 1$ , $1\le m\le 40$ ;对于任意 $1\le i\le n$ ：$1\le st_i\le 20$ , $1\le w_i\le 20$ , $1\le k_i\le 40$ , $1\le t_{i,j}\le 20$ , $1\le a_{i,j}\le m$ ,且保证：$a_{i,j_1}\neq a_{i,j_2}\quad(j_1\neq j_2)$ .
solution
题意概括
这道题本质上是一道细节比较多的模拟题。系统里有 n 个进程和 m 种资源，每个进程会从自己的 st_i 段开始活动，然后按照任务列表依次执行。对于第 j 个任务，进程要先申请资源 a[i][j]，申请成功之后才会运行这个任务，运行时间为 t[i][j] 段。
题目把每一段拆成了三个部分：段首负责申请资源和 C 类抢夺资源，段中负责计算正在运行进程的收益，段末负责结束任务和释放资源。因此写代码时最重要的一件事，就是严格按照这个顺序模拟。只要段首、段中、段末的时机没有混乱，后面的实现就会清楚很多。
最终输出每个进程的总收益以及运行段数。如果系统一直无法结束，就认为被强制终止，对还没有完成的进程输出 -1。虽然题面中写的是最多运行到 10^100 段，但数据范围很小，真正要处理的不是这个大数，而是判断系统是否进入了重复状态。
状态设计
每个进程在任意时刻只会处于几种状态之一：还没开始、正在申请资源、正在运行任务、已经结束。所以可以直接用一个整数数组 sta[i] 记录状态：
1 | 0 尚未开始 |
除此之外，还需要知道进程当前走到了任务列表的哪一项。这里用 cur[i] 表示当前任务编号，用 lef[i] 表示当前任务还剩多少段没有运行。对于 A/B/C 三类特殊进程，还要记录它连续申请当前资源失败了多少次，所以用 failc[i] 来保存失败次数。收益和结束时间分别用 ans[i]、finseg[i] 记录。
资源的归属也可以直接用数组表示。own[r] 表示资源 r 当前被哪个进程占有，如果 own[r]=0，说明这个资源处于待使用状态。由于 m <=40，每次需要计算某个进程当前拥有多少资源时，直接扫一遍所有资源即可，写起来简单，也不会有性能压力。
整体上，核心数组如下：
1 | sta[i] 进程状态 |
整体模拟架构
主循环按照段数从小到大枚举，每一段都严格拆成三步。先把这一段开始活动的进程激活为申请状态，然后处理段首申请和抢夺，再计算段中收益，最后在段末处理任务完成和资源释放。
大致流程如下：
1 | for (long long seg=1;; seg++) { |
这里的 rel[i] 是一个临时数组，用来标记 A 类进程是否需要在本段段末释放资源。之所以不在申请失败时立刻释放，是因为题目明确规定 A 类释放发生在第 s+w_i-1 段段末，而不是段首。
代码实现思路
代码整体没有做复杂封装，而是按照竞赛写法拆成几个小函数。读代码时可以先抓住三个阶段函数：apply_part()、middle_part()、end_part()。它们分别对应题目中的段首、段中、段末。主函数里的循环只是负责按顺序调用这三个函数，并在每段开始时激活新进程，在每段结束后判断是否完成或者进入循环。
几个辅助函数主要是为了减少重复代码。res(i) 返回进程 i 当前任务需要申请的资源，也就是 a[i][cur[i]]；dur(i) 返回当前任务持续时间，也就是 t[i][cur[i]]。当一个进程开始运行时，不管它是普通申请成功、B 类放弃资源后运行，还是 C 类抢夺后运行，都可以统一调用 start_run()。这个函数会把进程状态改成运行状态，设置剩余运行时间，并清空连续失败次数。区别只在于它的第二个参数：如果真的拿到了资源，就传 true；如果是 B 类放弃资源开始运行，或者 C 类抢夺失败后开始运行，就不会通过这个参数获得资源。
资源释放也被单独写成了 release_all(x)。因为有两个地方会释放进程占有的全部资源：一种是进程完成所有任务时停止活动，另一种是 A 类进程达到忍耐限度后在段末释放资源。把它写成函数之后，段末逻辑会比较直观。
申请失败的处理集中在 fail_apply() 中。这个函数先判断进程类型，如果是普通进程 X，申请失败不会改变额外状态；如果是特殊进程，就累加 failc[x]。当 A 类达到忍耐限度时，只给 rel[x] 打标记，等待段末释放；当 B 类达到忍耐限度时，直接调用 start_run(x, false) 让它进入运行状态。C 类在这里没有额外分支，因为 C 类的动作发生在下一段段首，代码会在下一次 apply_part() 开头根据 failc[i] >=w[i] 统一处理。
这样拆完之后，主循环的逻辑就比较接近题面描述：先激活进程，然后 apply_part(rel) 解决所有段首资源变化，接着 middle_part() 按当前资源归属统计收益，最后 end_part(seg, rel) 处理任务结束和 A 类释放。换句话说，代码结构是直接贴着题目的时间线写的，这样比把所有情况揉在一个大循环里更不容易漏掉时机细节。
段首处理
段首是这题最值得仔细处理的地方，因为普通申请和 C 类抢夺并不是完全平行的。题目规定，如果某个资源在本段存在 C 类抢夺，那么其他类型对该资源的普通申请全部失败。因此实现时可以先处理所有 C 类抢夺，再处理普通申请。
对于 C 类进程，如果它还处于申请状态，并且 failc[i] >=w[i]，说明它已经连续失败了 w_i 次，那么本段段首就要进行抢夺。代码中用 rob[r] 存下所有想要抢夺资源 r 的 C 类进程。若同一个资源有多个 C 类同时抢夺，则编号最大的进程成功获得资源：
1 | int win=*max_element(rob[r].begin(), rob[r].end()); |
这里有一个容易漏掉的细节：抢夺失败的 C 类进程虽然没有获得资源，但仍然会切换到任务运行状态。因此对于 rob[r] 中的所有进程，都要设置为运行状态，并初始化它们当前任务的剩余时间。只有 own[r] 最终归属于编号最大的那个进程。
处理完 C 类抢夺后，再收集所有仍处于申请状态的进程，放到 ask[r] 中，表示这些进程正在普通申请资源 r。对于每个资源，如果本段发生过 C 类抢夺，或者这个资源已经被占用，那么所有普通申请者都失败。否则，编号最小的申请者成功获得资源，其余申请者失败。
成功申请资源时调用：
1 | start_run(win, true); |
这里第二个参数表示是否真的获得了当前申请的资源。普通申请成功时当然是 true，而 B 类进程放弃资源后开始运行时会传 false。
特殊进程的失败逻辑
普通进程 X 申请失败后没有额外操作，只会在下一段继续申请同一个资源。特殊进程则需要累计连续失败次数，每次申请失败时执行：
1 | failc[x]++; |
A 类进程达到忍耐限度后，会在本段段末释放自己已经拥有的全部资源，并继续保持申请状态。因为释放不是立刻发生的，所以代码里只是先做一个标记：
1 | rel[x]=1; |
到了 end_part() 里，再根据这个标记调用 release_all(i)。释放后它不会回头补申请之前放弃掉的资源，而是继续申请当前卡住的资源，这一点正好可以通过“只释放资源、不改变 cur[i]”自然表示。
B 类进程达到忍耐限度后，会直接放弃当前资源，并从本段段中开始运行对应任务。所以在段首发现它失败次数达到 w_i 时，直接把它切换到运行状态即可：
1 | start_run(x, false); |
这里传入 false，表示它开始运行任务，但没有拿到这个任务本来想申请的资源，因此后续收益会少一些。
C 类进程和 A/B 类不同。它不是在第 w_i 次失败的当段立刻行动，而是在下一段段首强行抢夺。所以失败处理函数里不需要专门处理 C 类，只要把 failc[i] 累加上去即可。下一段进入 apply_part() 时，会通过 failc[i] >=w[i] 判断它是否该抢夺。
段中收益
段中只需要枚举所有正在运行的进程。每个运行进程在这一段获得的收益，等于它在本段段首处理完申请和抢夺之后实际拥有的资源数量。于是直接统计 own[] 中有多少资源属于该进程：
1 | ans[i]+=cnt_res(i); |
如果某个进程的资源在段首被 C 类抢走，它本身仍然可能处于运行状态，但拥有资源数已经变少，收益自然也会下降。这与题目中“被抢夺资源的进程运行状态不受影响”的描述是一致的。
段末处理
段末主要做两件事：第一，处理运行任务结束的进程；第二，处理本段触发 A 类机制的进程。
对于正在运行且 lef[i]==0 的进程，说明当前任务已经在本段段中运行完毕。如果这已经是它的最后一个任务，那么它会在本段段末停止活动，并释放自己占有的所有资源，同时记录完成段数 finseg[i]=seg。如果后面还有任务，则把它切换回申请状态，下一段段首开始申请下一个任务的资源。
A 类释放放在任务结束处理之后。若 rel[i] 被标记，并且该进程此时仍然处于申请状态，就释放它当前拥有的全部资源，并清空连续失败次数。这里判断 sta[i]==1 是为了保证只对仍在申请状态的 A 类进程执行释放，避免同一段内状态已经变化后重复处理。
为什么要判重
题目说系统最多会运行到 10^100 段，这个数字显然不能直接模拟。好在本题数据范围很小，而且系统的状态数量是有限的。一个完整状态包含所有资源的归属、每个进程的状态、当前任务编号、剩余运行时间以及连续失败次数。
当所有进程都已经到达开始时间之后，系统不会再出现新的外部启动事件。如果此时某个段末状态再次出现，那么从下一段开始，申请、运行、释放都会和上一次完全一样，系统会进入循环，不可能再产生新的结果。因此可以用 unordered_set<string> 保存每段段末状态：
1 | unordered_set<string> vis; |
当 seg >=maxst 时，说明所有进程都已经有机会被激活。从这时开始记录状态，如果发现状态重复，就可以停止模拟。最后输出时，已经完成的进程输出正常运行段数，尚未完成的进程输出 -1。
正确性说明
首先，程序的主循环顺序与题目完全一致。每一段都先处理段首行为，再处理段中收益，最后处理段末释放和任务结束。由于题目中所有规则都绑定在这三个时刻上，只要每个阶段内部处理正确，整体时间顺序就是正确的。
对于普通申请，程序按资源分别收集所有申请者。如果该资源本段被 C 类抢夺过，或者资源本来就已经被占有，则所有普通申请者失败；否则选择编号最小的进程成功获得资源。这正好对应题目对普通申请冲突的规定。
对于 C 类抢夺，程序在普通申请之前统一处理。若多个 C 类抢同一个资源，则取编号最大的进程作为资源拥有者；其他参与抢夺的 C 类进程虽然没有获得资源，也会进入运行状态。同时程序用 has_rob[r] 标记资源 r 本段发生过抢夺，从而让本段对该资源的普通申请全部失败，因此 C 类规则被完整模拟。
A 类和 B 类的触发时机也与题意一致。A 类达到失败次数后只设置段末释放标记，真正释放发生在 end_part()；B 类达到失败次数后立刻放弃当前资源并进入运行状态，所以从本段段中开始产生收益。C 类只累计失败次数，等到下一段段首再抢夺，也符合题目描述。
收益计算发生在段中，且使用的是段首处理完成后的资源归属 own[]。所以无论资源是普通申请得到的、被 C 类抢到的，还是从某个运行进程手里被抢走的，都会自然反映到当段收益中。任务剩余时间也在段中减少，段末再判断是否完成，时机与题目一致。
最后，判重不会误判。因为在 seg >=maxst 之后，不会再有新进程首次启动，系统转移只由当前状态决定。若段末完整状态重复，之后的所有行为都会周期性重复，系统不可能突然结束。因此发现重复状态时停止模拟，并把未完成进程输出为 -1 是正确的。
复杂度分析
设模拟过程中出现的不同完整状态数量为 S。每一段中，我们会扫描进程、扫描资源，并在计算收益时对每个运行进程统计一次资源数量。由于 n <=10、m <=40，单段复杂度可以粗略看作 O(nm)，总时间复杂度为：
1 | O(S * n * m) |
空间上主要是保存已经出现过的状态，所以空间复杂度为 O(S)。在本题数据范围下，这样的直接模拟足够通过。
完整代码
1 |
|
