oj.uz

답안 #448062

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
448062 2021-07-28T16:59:10 Z MohamedFaresNebili Job Scheduling (CEOI12_jobs) C++14
100 / 100
 350 ms 25020 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>

int n, d, m;

bool works(int robots, vector<pii> jobs)
{
    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;
    }
    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';

    const int hi = 1e5+12;
    vector<int> ans[hi];
    int endT[l] = {0};

    for (int i = 0, cur = 0; i < m; i++, cur++) {
        if (cur == l)
            cur = 0;
        endT[cur] = max(jobs[i].f, endT[cur]+1);
        ans[endT[cur]].push_back(jobs[i].s);
    }

    for (int i = 1; i <= n; i++) {
        for (int x: ans[i])
            cout << x << ' ';
        cout << "0\n";
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 4980 KB Output is correct
2 Correct 30 ms 4940 KB Output is correct
3 Correct 31 ms 4964 KB Output is correct
4 Correct 28 ms 4932 KB Output is correct
5 Correct 29 ms 4916 KB Output is correct
6 Correct 29 ms 5000 KB Output is correct
7 Correct 34 ms 4928 KB Output is correct
8 Correct 29 ms 4924 KB Output is correct
9 Correct 39 ms 5172 KB Output is correct
10 Correct 39 ms 5192 KB Output is correct
11 Correct 36 ms 4964 KB Output is correct
12 Correct 73 ms 7972 KB Output is correct
13 Correct 110 ms 9832 KB Output is correct
14 Correct 153 ms 13016 KB Output is correct
15 Correct 186 ms 14840 KB Output is correct
16 Correct 230 ms 17384 KB Output is correct
17 Correct 277 ms 20056 KB Output is correct
18 Correct 302 ms 22992 KB Output is correct
19 Correct 350 ms 25020 KB Output is correct
20 Correct 268 ms 19812 KB Output is correct