oj.uz

Submission #404233

# Submission time Handle Problem Language Result Execution time Memory
404233 2021-05-14T01:30:35 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
43 / 100
 468 ms 29044 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;
        int id = max(jobs[i].f, endT[cur]+1);
        ans[id].push_back(jobs[i].s);
        // 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';
    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 38 ms 5724 KB Partially correct
2 Partially correct 38 ms 5760 KB Partially correct
3 Partially correct 38 ms 5660 KB Partially correct
4 Partially correct 39 ms 5652 KB Partially correct
5 Partially correct 46 ms 5740 KB Partially correct
6 Partially correct 38 ms 5688 KB Partially correct
7 Partially correct 38 ms 5676 KB Partially correct
8 Partially correct 39 ms 5736 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 5480 KB Partially correct
12 Partially correct 101 ms 8580 KB Partially correct
13 Partially correct 168 ms 11936 KB Partially correct
14 Partially correct 205 ms 16260 KB Partially correct
15 Partially correct 241 ms 17884 KB Partially correct
16 Partially correct 311 ms 22764 KB Partially correct
17 Partially correct 374 ms 27328 KB Partially correct
18 Correct 430 ms 26384 KB Output is correct
19 Partially correct 468 ms 29044 KB Partially correct
20 Partially correct 379 ms 27356 KB Partially correct