oj.uz

Submission #404229

# Submission time Handle Problem Language Result Execution time Memory
404229 2021-05-14T01:20:58 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
55 / 100
 514 ms 28988 KB 
// 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>

const int hi = 1e5;

int n, d, m;
vector<int> ans[hi];

bool works(int robots, vector<pii> jobs)
{
    for (int i = 0; i < n; i++)
        ans[i].clear();

    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;
        ans[endT[cur]].push_back(jobs[i].s);
    }
    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';
    for (int i = 0; i < n; i++) {
        for (int x: ans[i])
            cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 5668 KB Partially correct
2 Partially correct 40 ms 5744 KB Partially correct
3 Partially correct 41 ms 5720 KB Partially correct
4 Partially correct 39 ms 5684 KB Partially correct
5 Partially correct 39 ms 5740 KB Partially correct
6 Partially correct 39 ms 5748 KB Partially correct
7 Partially correct 45 ms 5696 KB Partially correct
8 Partially correct 45 ms 5740 KB Partially correct
9 Partially correct 51 ms 5812 KB Partially correct
10 Partially correct 53 ms 5936 KB Partially correct
11 Partially correct 47 ms 5452 KB Partially correct
12 Partially correct 96 ms 8504 KB Partially correct
13 Correct 172 ms 11968 KB Output is correct
14 Partially correct 208 ms 16228 KB Partially correct
15 Partially correct 262 ms 17784 KB Partially correct
16 Correct 317 ms 22748 KB Output is correct
17 Correct 377 ms 27344 KB Output is correct
18 Correct 436 ms 26316 KB Output is correct
19 Partially correct 514 ms 28988 KB Partially correct
20 Correct 403 ms 27356 KB Output is correct