Submission #719278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
719278	2023-04-05T17:22:16 Z	thimote75	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	464 ms	12140 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	41 ms	2256 KB	Output is correct
2	Correct	36 ms	2256 KB	Output is correct
3	Correct	42 ms	2344 KB	Output is correct
4	Correct	42 ms	2372 KB	Output is correct
5	Correct	37 ms	2340 KB	Output is correct
6	Correct	39 ms	2324 KB	Output is correct
7	Correct	42 ms	2328 KB	Output is correct
8	Correct	37 ms	2320 KB	Output is correct
9	Correct	159 ms	1876 KB	Output is correct
10	Correct	148 ms	1876 KB	Output is correct
11	Correct	35 ms	1876 KB	Output is correct
12	Correct	72 ms	3256 KB	Output is correct
13	Correct	113 ms	5708 KB	Output is correct
14	Correct	154 ms	6076 KB	Output is correct
15	Correct	179 ms	6444 KB	Output is correct
16	Correct	209 ms	11004 KB	Output is correct
17	Correct	278 ms	11336 KB	Output is correct
18	Correct	321 ms	11760 KB	Output is correct
19	Correct	464 ms	12140 KB	Output is correct
20	Correct	264 ms	11392 KB	Output is correct