死锁优化

GitHub跳转原题关系图 Canvas 关系图返回列表

按时间段模拟资源申请、特殊进程的放弃与抢夺，并用状态循环判断无法结束的死锁。

OJ: shumeng

题目 ID: CSP202605C

难度:未知

标签:模拟状态机哈希多进程调度

日期: 2026-07-31 16:22

形式化题目

$n$ 个进程、 $m$ 种资源，每个进程从第 $st_i$ 段首开始活动，按任务列表依次申请资源并运行，任务长度 $t_{i,j}$ 段。每段分为段首（申请）、段中（收益）、段末（推进/释放）。

同一资源同一段首被多进程申请时：资源空闲则编号最小者成功，否则全部失败；
A 类：连续 $w$ 次申请失败后，在段末释放自己占有的全部资源，继续等待；
B 类：连续 $w$ 次申请失败后，直接放弃该资源并进入运行；
C 类：连续 $w$ 次申请失败后在段首强行抢夺，多个 C 同时抢夺时编号最大者成功。

运行中的进程每段获得等于其当前持有资源数的收益。输出每个进程的总收益与运行段数；若系统因死锁被强制结束，输出 -1。

思路

三个阶段逐一模拟

每段严格按“段首申请 → 段中收益 → 段末推进和释放”推进。进程维护状态、当前任务、等待开始时间、剩余段数与收益；资源维护当前占有者。

段首的统一处理

同一资源的申请必须收集到一起后一次性处理，不能按进程编号顺序修改资源状态，否则后面的进程会看到前面进程刚改过的状态：

若本段有到期的 C 类进程（等待已达 $w$ ），编号最大者抢占资源，其余 C 类申请失败但仍进入运行；
否则若资源空闲，编号最小的申请者成功；
B 类第 $w$ 次失败直接进入运行；A 类第 $w$ 次失败打上“段末释放”标记。

text

1
2
3段首申请:  收集 requests -> 优先 C 抢夺 -> 空闲则最小号成功 -> 记录 B 放弃 / A 待释放
段中收益:  运行进程 gain += 当前持有资源数, remain--
段末推进:  A 释放全部资源 -> 任务结束则释放并完成 / 否则进入下一任务

死锁检测

没有 C 类进程时系统可能陷入死锁。所有进程开始后，若某个完整系统状态（各进程的阶段、任务、等待时长与资源归属）再次出现，则之后必然无限循环，直接终止并把未完成的进程标为 -1。用哈希集合记录状态即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:22
 * update_at: 2026-08-17 22:40
 */
#include <bits/stdc++.h>
using namespace std;

// 一个进程的全部运行信息
struct Process {
    char type;       // 进程类型 X / A / B / C
    int start_time;  // 开始活动的段首
    int patience;    // 忍耐限度 w
    vector<int> resource; // 每个任务要申请的资源
    vector<int> duration; // 每个任务的持续段数
    int task;        // 当前正在执行第几个任务（从 0 开始）
    int state; // 0: 未开始，1: 申请资源，2: 运行，3: 完成
    int wait_start;  // 本轮等待开始的段首
    int remain;      // 当前任务剩余运行段数
    long long gain;  // 累计收益
    long long finish_time; // 完成时的段号，-1 表示未正常结束
};

vector<Process> process_list; // 1 下标
int owner[41];                // 每种资源当前的占有者，0 表示待使用
bool owns[11][41];            // 进程 i 是否占有资源 j

// 进程 process 抢占资源 resource，把原占有者从该资源上挤掉。
void acquire_resource(int process, int resource) {
    if (owner[resource] != 0) {
        owns[owner[resource]][resource] = false;
    }
    owner[resource] = process;
    owns[process][resource] = true;
}

void release_all(int process) {
    for (int resource = 1; resource <= 40; resource++) {
        if (owns[process][resource]) {
            owns[process][resource] = false;
            owner[resource] = 0;
        }
    }
}

// 计算当前完整系统状态的哈希，用于检测死锁循环。
// 状态包含每个进程的阶段/任务/剩余段数/等待时长以及每种资源的占有者。
unsigned long long state_hash(int current_time, int max_start, int resource_count) {
    unsigned long long result = 1469598103934665603ULL;
    for (int i = 1; i < (int)process_list.size(); i++) {
        Process &process = process_list[i];
        int age = 0;
        if (process.state == 1) {
            age = current_time - process.wait_start;
            if (process.type != 'X') age = min(age, process.patience + 1);
            else age = min(age, 1);
        }
        result ^= (unsigned long long)(process.state + 5 * process.task +
            31 * process.remain + 997 * age + 10007 * i);
        result *= 1099511628211ULL;
    }
    for (int resource = 1; resource <= resource_count; resource++) {
        result ^= (unsigned long long)(owner[resource] + 131 * resource);
        result *= 1099511628211ULL;
    }
    if (current_time <= max_start) result ^= (unsigned long long)current_time;
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, resource_count;
    cin >> n >> resource_count;
    process_list.resize(n + 1);
    int max_start = 0;
    for (int i = 1; i <= n; i++) {
        Process &process = process_list[i];
        cin >> process.type;
        int task_count;
        if (process.type == 'X') {
            cin >> process.start_time >> task_count;
            process.patience = 0;
        } else {
            cin >> process.start_time >> process.patience >> task_count;
        }
        max_start = max(max_start, process.start_time);
        process.resource.resize(task_count);
        process.duration.resize(task_count);
        for (int j = 0; j < task_count; j++) {
            cin >> process.resource[j] >> process.duration[j];
        }
        process.task = 0;
        process.state = 0;
        process.wait_start = 0;
        process.remain = 0;
        process.gain = 0;
        process.finish_time = -1;
    }

    memset(owner, 0, sizeof(owner));
    memset(owns, 0, sizeof(owns));
    unordered_set<unsigned long long> visited;
    long long current_time = 1;
    int finished = 0;
    while (finished < n) {
        for (int i = 1; i <= n; i++) {
            if (process_list[i].state == 0 &&
                process_list[i].start_time <= current_time) {
                process_list[i].state = 1;
                process_list[i].wait_start = (int)current_time;
            }
        }

        if (current_time > max_start) {
            unsigned long long hash =
                state_hash((int)current_time, max_start, resource_count);
            if (!visited.insert(hash).second) break;
        }

        // 段首：先收集所有处于申请状态的进程对资源的请求。
        // 同一资源的所有申请必须一起处理，不能按进程编号逐个修改资源状态。
        vector<int> requests[41];
        for (int i = 1; i <= n; i++) {
            if (process_list[i].state == 1) {
                int resource = process_list[i].resource[process_list[i].task];
                requests[resource].push_back(i);
            }
        }

        // release_after 标记段末需要释放全部资源的进程（A 类放弃行为）
        vector<int> release_after(n + 1, 0);
        for (int resource = 1; resource <= resource_count; resource++) {
            if (requests[resource].empty()) continue;
            vector<int> forced;
            for (int j = 0; j < (int)requests[resource].size(); j++) {
                int process_id = requests[resource][j];
                Process &process = process_list[process_id];
                if (process.type == 'C' &&
                    current_time >= process.wait_start + process.patience) {
                    forced.push_back(process_id);
                }
            }

            if (!forced.empty()) {
                int winner = *max_element(forced.begin(), forced.end());
                for (int j = 0; j < (int)forced.size(); j++) {
                    int process_id = forced[j];
                    Process &process = process_list[process_id];
                    if (process_id == winner) acquire_resource(process_id, resource);
                    process.state = 2;
                    process.remain = process.duration[process.task];
                }
                for (int j = 0; j < (int)requests[resource].size(); j++) {
                    int process_id = requests[resource][j];
                    bool is_forced = false;
                    for (int u = 0; u < (int)forced.size(); u++) {
                        if (forced[u] == process_id) is_forced = true;
                    }
                    if (is_forced) continue;
                    Process &process = process_list[process_id];
                    if (process.type == 'B' &&
                        current_time >= process.wait_start + process.patience - 1) {
                        process.state = 2;
                        process.remain = process.duration[process.task];
                    } else if (process.type == 'A' &&
                        current_time >= process.wait_start + process.patience - 1) {
                        release_after[process_id] = 1;
                    }
                }
            } else if (owner[resource] == 0) {
                int winner = *min_element(requests[resource].begin(),
                    requests[resource].end());
                for (int j = 0; j < (int)requests[resource].size(); j++) {
                    int process_id = requests[resource][j];
                    Process &process = process_list[process_id];
                    if (process_id == winner) {
                        acquire_resource(process_id, resource);
                        process.state = 2;
                        process.remain = process.duration[process.task];
                    } else if (process.type == 'B' &&
                        current_time >= process.wait_start + process.patience - 1) {
                        process.state = 2;
                        process.remain = process.duration[process.task];
                    } else if (process.type == 'A' &&
                        current_time >= process.wait_start + process.patience - 1) {
                        release_after[process_id] = 1;
                    }
                }
            } else {
                for (int j = 0; j < (int)requests[resource].size(); j++) {
                    int process_id = requests[resource][j];
                    Process &process = process_list[process_id];
                    if (process.type == 'B' &&
                        current_time >= process.wait_start + process.patience - 1) {
                        process.state = 2;
                        process.remain = process.duration[process.task];
                    } else if (process.type == 'A' &&
                        current_time >= process.wait_start + process.patience - 1) {
                        release_after[process_id] = 1;
                    }
                }
            }
        }

        // 段中：处于运行状态的进程获得等于当前持有资源数的收益，并消耗一段运行时间
        for (int i = 1; i <= n; i++) {
            Process &process = process_list[i];
            if (process.state == 2) {
                int held_count = 0;
                for (int resource = 1; resource <= resource_count; resource++) {
                    if (owns[i][resource]) held_count++;
                }
                process.gain += held_count;
                process.remain--;
            }
        }

        for (int i = 1; i <= n; i++) {
            Process &process = process_list[i];
            if (release_after[i]) {
                release_all(i);
                process.wait_start = (int)current_time + 1;
            }
            if (process.state == 2 && process.remain == 0) {
                process.task++;
                if (process.task == (int)process.resource.size()) {
                    process.state = 3;
                    process.finish_time = current_time;
                    release_all(i);
                    finished++;
                } else {
                    process.state = 1;
                    process.wait_start = (int)current_time + 1;
                }
            }
        }
        current_time++;
    }

    for (int i = 1; i <= n; i++) {
        if (process_list[i].state == 3) {
            cout << process_list[i].gain << ' '
                 << process_list[i].finish_time - process_list[i].start_time + 1 << '\n';
        } else {
            cout << process_list[i].gain << " -1\n";
        }
    }
    return 0;
}

复杂度

时间：每段需要 $O(nm)$ 处理请求与统计收益，本题 $n\le 10,\ m\le 40$ ，模拟段数有界。
空间： $O(nm)$ ，加上死锁检测使用的哈希集合。

总结

资源申请必须按段首的同时性统一处理，不能按进程编号依次修改资源状态；把每一段拆成“申请、收益、推进”三个阶段即可准确模拟特殊规则。死锁检测的关键是识别出完整系统状态的循环。

题目来自第 42 次 CSP 认证 T3，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

西西艾弗岛上，小 F 的团队每天都在忙碌着。他们在解决了进程与接口的通信问题后，开始着手进行进程间资源使用与调度系统的开发。项目开展一段时间后，他们又把你这个资深测试员叫了过来。按照惯例，他们给出了这次资源调度系统的运行模型，并请求你为其编写程序进行模拟。

题目描述

模型中需要考虑的对象有 $n$ 个进程与 $m$ 种资源。进程由 $1,2,\cdots,n$ 依次标号，资源由 $1,2,\cdots,m$ 依次标号。

该系统运行的时间单位称作段。每一段分为“申请”“处理”“释放”三个部分（本题亦称其“段首”“段中”“段末”），在时间轴上体现如下：

申请部分（段首）专门处理进程对资源的申请行为，在处理部分（段中）每个进程会产生各自的收益，释放部分（段末）专门负责将资源从进程中释放到待使用区。

系统会依次运行第 $1,2,\cdots,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}$ 两两不同。

单进程行为与收益

一个进程分为资源申请状态和任务运行状态。刚从某段首开始活动的进程初始为资源申请状态。

在某一段首，一个处于资源申请状态的进程会向其当前所需的某资源发起申请。
在某一段中，一个处于任务运行状态的进程会获得收益，收益量等于其在该段段首运行完毕后拥有的资源数量。

在没有任何干扰，资源可以由某 $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\limits_{j=1}^{k_i} t_{i,j}-1$ 段末完成所有运行任务并停止活动。在这一段末， $i$ 号进程会释放所有其使用的资源，也即资源 $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$ 均不再被占有，而是变为待使用状态。

根据定义，上述过程 $i$ 号进程从开始活动到结束的理想总收益为 $\sum\limits_{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$ 。

input1

1
2
3
43 5
X 1 3 1 3 3 4 4 3
B 2 2 4 2 1 1 2 5 3 3 2
C 3 3 2 1 2 4 2

output1

样例 1 解释

下面列出该样例中涉及的特殊事件：

第 $3\sim 4$ 段首 $2$ 号进程申请资源 $1$ 均失败，故其放弃申请 $1$ 号资源，从第 $4$ 段中起仅占用资源 $2$ 运行第二个任务至第 $5$ 段末。

第 $9\sim 10$ 段首 $2$ 号进程申请资源 $3$ 均失败，故其放弃申请 $3$ 号资源，从第 $10$ 段中起仅占用资源 $2,5$ 运行第四个任务至第 $11$ 段末。

第 $3\sim 5$ 段首， $3$ 号进程申请资源 $1$ 均失败，故于第 $6$ 段首将 $1$ 号资源抢夺并占有 $1$ 号资源运行第一个任务至第 $7$ 段末；第 $8$ 段首与 $1$ 号进程同时申请 $4$ 号资源因为编号较大失败，持续到第 $10$ 段首。第 $11$ 段首 $3$ 号进程抢夺了刚刚在第 $10$ 段末被 $1$ 号进程释放到待使用区的 $4$ 号资源，并占用资源 $1,4$ 运行第二个任务至第 $12$ 段末。

从图中可以看出三个进程的运行段数均为 $10$ 。

input2

1
2
3
4
5
6
7
8
9
10
1110 40
X 6 32 13 7 2 18 10 4 25 3 1 7 28 10 37 10 32 16 30 8 16 11 19 11 29 12 33 4 39 5 24 5 34 10 27 4 38 20 21 8 18 2 9 16 20 17 23 17 35 11 31 14 8 20 7 17 12 19 6 1 5 19 3 10 22 12
X 10 17 35 5 20 17 30 1 9 2 12 8 34 4 28 17 18 15 22 17 1 7 7 7 24 4 5 15 31 4 2 4 25 20 3 20
X 4 33 38 3 17 6 16 19 21 7 23 17 22 4 11 12 7 3 1 4 24 11 35 20 26 6 33 7 8 11 13 4 25 17 4 5 40 9 39 18 18 9 5 6 9 2 14 14 34 10 28 2 32 3 2 14 30 9 27 8 3 3 29 11 19 7 36 6
X 20 6 31 15 19 4 1 11 3 12 8 14 15 13
X 8 28 19 6 1 20 22 6 16 17 14 3 34 14 3 19 40 5 10 5 27 9 6 2 13 14 35 6 26 8 18 10 23 10 20 12 2 7 30 20 39 3 36 6 4 10 17 5 5 16 38 13 28 11 33 4 29 5
X 19 26 35 14 10 5 17 15 5 18 6 1 38 20 4 4 3 18 31 11 20 1 22 3 39 15 7 11 27 7 8 19 16 2 32 9 26 15 25 6 28 15 1 10 23 8 34 14 30 8 29 15 9 19
X 6 6 22 20 37 9 27 7 13 7 16 6 14 19
X 5 8 5 1 14 8 6 4 11 7 37 7 9 10 20 20 18 17
X 7 2 3 3 40 9
X 1 3 3 18 31 15 12 16

output2

子任务

对于前 $40\%$ 的测试数据，保证不存在特殊类型的进程。

对于另外 $40\%$ 的测试数据，保证不存在 C 类进程。

对于 $100\%$ 的测试数据，保证 $1\leq n\leq 10,1\leq m\leq 40$ 。 $\forall 1\leq i\leq n$ 有 $1\leq st_i\leq 20,1\leq w_i\leq 20,1\leq k_i\leq 40,1\leq t_{i,j}\leq 20,1\leq a_{i,j}\leq m$ ，且保证 $\forall j_1\neq j_2,a_{i,j_1}\neq a_{i,j_2}$ 。

死锁优化

目录

形式化题目

思路

三个阶段逐一模拟

段首的统一处理

死锁检测

代码

复杂度

总结