Submission #441756

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441756	2021-07-06T03:44:07 Z	Yuisuyuno	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	364 ms	24908 KB

jobs

// Author : Jad Isaac
// ID: jadDebugs
// TASK: -----
// LANG: C++                 

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<int, int>

int n, d, m;

bool works(int robots, vector<pii> jobs)
{
    int endT[robots] = {0};
    int maxD = 0;

    for (int i = 0, cur = 0; i < m; i++, cur++) {
        if (cur == robots)
            cur = 0;
        // if our end time for this job is > than our start time for this job
        // there will be delay
        if (endT[cur] + 1 > jobs[i].f) {
            endT[cur]++;
            maxD = max(maxD, endT[cur] - jobs[i].f);
        }
        else
            endT[cur] = jobs[i].f;
    }
    return maxD <= d;
}

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

    cin >> n >> d >> m;

    // first = day of req
    // second = id or req
    vector<pii> jobs(m);

    for (int i = 0; i < m; i++) {
        cin >> jobs[i].f;
        jobs[i].s = i+1;
    }
    sort(begin(jobs), end(jobs));
    int l = 0, r = m;

    while (l < r) {
        int mid = l + (r-l)/2;
        if (works(mid, jobs))
            r = mid;
        else
            l = mid+1;
    }
    cout << l << '\n';

    const int hi = 1e5+12;
    vector<int> ans[hi];
    int endT[l] = {0};

    for (int i = 0, cur = 0; i < m; i++, cur++) {
        if (cur == l)
            cur = 0;
        endT[cur] = max(jobs[i].f, endT[cur]+1);
        ans[endT[cur]].push_back(jobs[i].s);
    }

    for (int i = 1; i <= n; i++) {
        for (int x: ans[i])
            cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	4916 KB	Output is correct
2	Correct	30 ms	4944 KB	Output is correct
3	Correct	40 ms	5020 KB	Output is correct
4	Correct	29 ms	4948 KB	Output is correct
5	Correct	29 ms	4940 KB	Output is correct
6	Correct	28 ms	5052 KB	Output is correct
7	Correct	29 ms	4940 KB	Output is correct
8	Correct	29 ms	4916 KB	Output is correct
9	Correct	39 ms	5100 KB	Output is correct
10	Correct	40 ms	5204 KB	Output is correct
11	Correct	37 ms	4932 KB	Output is correct
12	Correct	73 ms	7460 KB	Output is correct
13	Correct	109 ms	9820 KB	Output is correct
14	Correct	155 ms	12408 KB	Output is correct
15	Correct	185 ms	14840 KB	Output is correct
16	Correct	233 ms	17288 KB	Output is correct
17	Correct	270 ms	19800 KB	Output is correct
18	Correct	309 ms	22220 KB	Output is correct
19	Correct	364 ms	24908 KB	Output is correct
20	Correct	273 ms	19740 KB	Output is correct