oj.uz

Submission #404230

# Submission time Handle Problem Language Result Execution time Memory
404230 2021-05-14T01:21:19 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
32 / 100
 415 ms 35144 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 = 1e4;

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
32.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 38 ms 3624 KB Partially correct
2 Partially correct 37 ms 3640 KB Partially correct
3 Partially correct 37 ms 3628 KB Partially correct
4 Partially correct 37 ms 3556 KB Partially correct
5 Partially correct 37 ms 3604 KB Partially correct
6 Partially correct 39 ms 3608 KB Partially correct
7 Partially correct 40 ms 3556 KB Partially correct
8 Partially correct 37 ms 3544 KB Partially correct
9 Runtime error 22 ms 4032 KB Execution killed with signal 11
10 Runtime error 23 ms 4036 KB Execution killed with signal 11
11 Partially correct 46 ms 3324 KB Partially correct
12 Partially correct 93 ms 6308 KB Partially correct
13 Correct 147 ms 9824 KB Output is correct
14 Runtime error 154 ms 20276 KB Execution killed with signal 11
15 Partially correct 246 ms 15660 KB Partially correct
16 Runtime error 241 ms 29188 KB Execution killed with signal 11
17 Runtime error 277 ms 35144 KB Execution killed with signal 11
18 Correct 415 ms 24264 KB Output is correct
19 Runtime error 210 ms 29380 KB Execution killed with signal 11
20 Runtime error 278 ms 35120 KB Execution killed with signal 11