AOJ 1361 Deadlock Detection
解法
求めるものは unavoidable になる境界なので二分探索できそうです.
ある時刻からデットロックを避ける最良の方法は,当然 terminate できるプロセスを順に殺していくことです.
愚直にやると殺せるプロセスを探索するのに O(p^2r) かかりそうですが,あらかじめリソースごとに必要な数でソートしておくと O(prlog(p)) でできるようになります.
計算量はトータル O( (t + prlogp)logt) になります.
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; int main() { int p, r, t; cin >> p >> r >> t; vector<int> l(r); vector<vector<int>> n(p, vector<int>(r)); vector<int> P(t), R(t); for(int i = 0; i < r; ++i) { cin >> l[i]; } for(int i = 0; i < p; ++i) { for(int j = 0; j < r; ++j) { cin >> n[i][j]; } } for(int i = 0; i < t; ++i) { cin >> P[i] >> R[i]; P[i]--; R[i]--; } int lb = 0, ub = t + 1; while(ub - lb > 1) { int m = (lb + ub) / 2; vector<int> available = l; vector<vector<pii>> need_r(r, vector<pii>(p)); vector<vector<int>> used_r(p, vector<int>(r)); vector<int> pos(r), cnt(p); queue<int> term_process; for(int i = 0; i < r; ++i) { for(int j = 0; j < p; ++j) { need_r[i][j] = make_pair(n[j][i], j); } } for(int i = 0; i < m; ++i) { available[R[i]]--; need_r[R[i]][P[i]].first--; used_r[P[i]][R[i]]++; } for(int i = 0; i < r; ++i) { sort(begin(need_r[i]), end(need_r[i])); } for(int i = 0; i < r; ++i) { while(pos[i] < p && (need_r[i][pos[i]].first == 0 || available[i] >= need_r[i][pos[i]].first)) { int process_id = need_r[i][pos[i]].second; if(++cnt[process_id] == r) { term_process.push(process_id); } pos[i]++; } } while(!term_process.empty()) { int idx = term_process.front(); term_process.pop(); for(int i = 0; i < r; ++i) { available[i] += used_r[idx][i]; while(pos[i] < p && available[i] >= need_r[i][pos[i]].first) { int process_id = need_r[i][pos[i]].second; if(++cnt[process_id] == r) { term_process.push(process_id); } pos[i]++; } } } if(count(begin(cnt), end(cnt), r) == p) { lb = m; } else { ub = m; } } if(ub == t + 1) { cout << -1 << endl; } else { cout << ub << endl; } }
感想
やるだけなんですがバグってしまった.