Submission #404237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
404237	2021-05-14T01:39:25 Z	jadDebugs	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	336 ms	23228 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+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	31 ms	4916 KB	Output is correct
2	Correct	28 ms	5020 KB	Output is correct
3	Correct	28 ms	4956 KB	Output is correct
4	Correct	29 ms	5004 KB	Output is correct
5	Correct	27 ms	4924 KB	Output is correct
6	Correct	34 ms	4936 KB	Output is correct
7	Correct	36 ms	4924 KB	Output is correct
8	Correct	27 ms	4924 KB	Output is correct
9	Correct	37 ms	4916 KB	Output is correct
10	Correct	44 ms	4924 KB	Output is correct
11	Correct	36 ms	4784 KB	Output is correct
12	Correct	70 ms	6964 KB	Output is correct
13	Correct	105 ms	9272 KB	Output is correct
14	Correct	167 ms	11584 KB	Output is correct
15	Correct	177 ms	13876 KB	Output is correct
16	Correct	224 ms	16176 KB	Output is correct
17	Correct	282 ms	18364 KB	Output is correct
18	Correct	327 ms	20740 KB	Output is correct
19	Correct	336 ms	23228 KB	Output is correct
20	Correct	266 ms	18420 KB	Output is correct