Problem: Example

Input

2 2 7
3 4
3 2
1 3
1 1
2 2
1 2
2 1
1 2
2 2
1 1


Output

5

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

int main(){
    int p,r,t;
    cin >> p >> r >> t;
    vector<int> resources(r);
    for(int i=0; i<r; i++){
        cin >> resources[i];
    }
    vector<vector<int>> needs(p, vector<int>(r));
    for(int i=0; i<p; i++){
        for(int j=0; j<r; j++){
            cin >> needs[i][j];
        }
    }
    auto needs_def = needs;
    vector<pair<int,int>> log(t);
    for(int i=0; i<t; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        log[i] = {a, b};
    }

    int ok=-1, ng=t;
    int prevmid=-1;
    while(ok+1 < ng){
        int mid = (ok+ng)/2;
        for(int i=prevmid; i<mid; i++){
            needs[log[i+1].first][log[i+1].second]--;
            resources[log[i+1].second]--;
        }
        for(int i=prevmid; i>mid; i--){
            needs[log[i].first][log[i].second]++;
            resources[log[i].second]++;
        }
        prevmid = mid;

        auto rsc = resources;
        vector<bool> terminated(p, false);
        int endnum = 0;
        for(int i=0; i<p; i++){
            if(*max_element(needs[i].begin(), needs[i].end()) == 0){
                terminated[i] = true;
                for(int j=0; j<r; j++){
                    rsc[j] += needs_def[i][j];
                }
                endnum++;
            }
        }
        while(endnum < p){
            bool deadlock = true;
            for(int i=0; i<p; i++){
                if(terminated[i]) continue;
                bool ok = true;
                for(int j=0; j<r; j++){
                    if(rsc[j] < needs[i][j]) ok = false;
                }
                if(ok){
                    terminated[i] = true;
                    deadlock = false;
                    for(int j=0; j<r; j++){
                        rsc[j] += needs_def[i][j] -needs[i][j];
                    }
                    endnum++;
                }
            }
            if(deadlock) break;
        }
        if(endnum == p){
            ok = mid;
        }else{
            ng = mid;
        }
    }
    if(ng == t){
        cout << -1 << endl;
    }else{
        cout << ng+1 << endl;
    }
    return 0;
}