Submission #719278

#	Time	Username	Problem	Language	Result	Execution time	Memory
719278		thimote75	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	464 ms	12140 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define di pair<int, int>

int nbDays, delay, nbJobs;

vector<di> jobs;
vector<int> days_processed;

bool process (int nbMachines) {
    queue<di> jobs_due;

    int cursor = 0;
    for (int idDay = 0; idDay < nbDays; idDay ++) {
        if (jobs_due.size() != 0 && jobs_due.front().first < idDay)
            return false;
        
        while (cursor != nbJobs && jobs[cursor].first == idDay) {
            jobs_due.push({ jobs[cursor].first + delay, jobs[cursor].second });
            cursor ++;
        }
        
        for (int idMac = 0; idMac < nbMachines && jobs_due.size() != 0; idMac ++) {
            di data = jobs_due.front();
            jobs_due.pop();

            days_processed[data.second] = idDay;
        }
    }

    return true;
}

int find_optimal () {
    int a = 0;
    int b = nbJobs;

    while (b - a > 1) {
        int c = (b + a) >> 1;

        if (process(c)) b = c;
        else a = c;
    }

    return b;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> nbDays >> delay >> nbJobs;
    days_processed.resize(nbJobs);

    for (int i = 0; i < nbJobs; i ++) {
        int x; cin >> x; x --;

        jobs.push_back({ x, i });
    }
    sort(jobs.begin(), jobs.end());

    int opti = find_optimal();
    cout << opti << endl;

    for (int i = 0; i < nbDays; i ++) cout << 0 << endl;
}

• Subtask 1: 100 / 100