oj.uz

Submission #404232

# Submission time Handle Problem Language Result Execution time Memory
404232 2021-05-14T01:25:19 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
43 / 100
 471 ms 29064 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+3;

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

Subtask #1
43.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 44 ms 5672 KB Partially correct
2 Partially correct 39 ms 5656 KB Partially correct
3 Partially correct 42 ms 5684 KB Partially correct
4 Partially correct 39 ms 5668 KB Partially correct
5 Partially correct 39 ms 5684 KB Partially correct
6 Partially correct 39 ms 5656 KB Partially correct
7 Partially correct 43 ms 5668 KB Partially correct
8 Partially correct 39 ms 5652 KB Partially correct
9 Partially correct 50 ms 5812 KB Partially correct
10 Partially correct 50 ms 5860 KB Partially correct
11 Partially correct 55 ms 5452 KB Partially correct
12 Partially correct 95 ms 8428 KB Partially correct
13 Partially correct 147 ms 11952 KB Partially correct
14 Partially correct 229 ms 16264 KB Partially correct
15 Partially correct 249 ms 17888 KB Partially correct
16 Partially correct 311 ms 22760 KB Partially correct
17 Partially correct 376 ms 27300 KB Partially correct
18 Correct 422 ms 26396 KB Output is correct
19 Partially correct 471 ms 29064 KB Partially correct
20 Partially correct 369 ms 27356 KB Partially correct