oj.uz

Submission #404231

# Submission time Handle Problem Language Result Execution time Memory
404231 2021-05-14T01:24:40 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
37 / 100
 490 ms 52100 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 = 1; i <= n; i++) {
        for (int x: ans[i])
            cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Subtask #1
37.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 40 ms 5692 KB Partially correct
2 Partially correct 38 ms 5660 KB Partially correct
3 Partially correct 38 ms 5724 KB Partially correct
4 Partially correct 38 ms 5672 KB Partially correct
5 Partially correct 38 ms 5736 KB Partially correct
6 Partially correct 38 ms 5752 KB Partially correct
7 Partially correct 40 ms 5732 KB Partially correct
8 Partially correct 38 ms 5692 KB Partially correct
9 Runtime error 65 ms 10992 KB Execution killed with signal 11
10 Runtime error 61 ms 11124 KB Execution killed with signal 11
11 Partially correct 56 ms 5476 KB Partially correct
12 Partially correct 94 ms 8484 KB Partially correct
13 Partially correct 150 ms 11972 KB Partially correct
14 Partially correct 223 ms 16356 KB Partially correct
15 Partially correct 255 ms 17868 KB Partially correct
16 Partially correct 315 ms 22760 KB Partially correct
17 Partially correct 381 ms 27368 KB Partially correct
18 Correct 433 ms 26352 KB Output is correct
19 Runtime error 490 ms 52100 KB Execution killed with signal 11
20 Partially correct 373 ms 27352 KB Partially correct