Submission #404236

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404236	2021-05-14T01:38:51 Z	jadDebugs	Job Scheduling (CEOI12_jobs)	C++14	85 / 100	362 ms	40132 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';

    int hi = 1e5;
    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

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	4916 KB	Output is correct
2	Correct	29 ms	4940 KB	Output is correct
3	Correct	28 ms	4924 KB	Output is correct
4	Correct	30 ms	4948 KB	Output is correct
5	Correct	28 ms	5052 KB	Output is correct
6	Correct	31 ms	5016 KB	Output is correct
7	Correct	28 ms	5020 KB	Output is correct
8	Correct	28 ms	4952 KB	Output is correct
9	Runtime error	43 ms	9156 KB	Execution killed with signal 11
10	Runtime error	42 ms	9140 KB	Execution killed with signal 11
11	Correct	36 ms	4748 KB	Output is correct
12	Correct	84 ms	6976 KB	Output is correct
13	Correct	108 ms	9240 KB	Output is correct
14	Correct	150 ms	11524 KB	Output is correct
15	Correct	178 ms	13884 KB	Output is correct
16	Correct	224 ms	16056 KB	Output is correct
17	Correct	262 ms	18348 KB	Output is correct
18	Correct	299 ms	20656 KB	Output is correct
19	Runtime error	362 ms	40132 KB	Execution killed with signal 11
20	Correct	264 ms	18352 KB	Output is correct