Submission #1128392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128392		ewang	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	462 ms	20160 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> ans(100001);

bool ok(int machines, vector<pair<int, int>>& t, int m, int d, int n) {
    for (int i = 1; i <= n; i++) {
        ans[i].clear();
    }

    // need to check if all tasks can be done at most D days after scheduled
    int req = 0;
    for (int day = 1; day <= n; day++) {
        for (int j = 0; j < machines; j++) {
            if (req == m) {
                return true;
            }
            
            if (t[req].first > day) {
                break;
            }
            
            if (day > t[req].first+d) {
                return false;
            }
            
            ans[day].push_back(t[req++].second);
        }
    }
    
    return true;
}

int main() {
    int n, d, m;
    cin >> n >> d >> m;
    
    vector<pair<int, int>> t(m);
    for (int i = 0; i < m; i++) {
        cin >> t[i].first;
        t[i].second = i+1;
    }
    sort(t.begin(), t.end());
    
    int lo = 1;
    int hi = m;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (ok(mid, t, m, d, n)) {
            hi = mid;
        } else {
            lo = mid+1;
        }
    }
    
    cout << lo << endl;
    
    ok(lo, t, m, d, n);
    for (int i = 1; i <= n; i++) {
        for (int task : ans[i]) {
            cout << task << " ";
        }
        cout << 0 << endl;
    }
    
    return 0;
}

• Subtask 1: 100 / 100