oj.uz

답안 #404237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404237 2021-05-14T01:39:25 Z jadDebugs Job Scheduling (CEOI12_jobs) C++14
100 / 100
 336 ms 23228 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';

    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 31 ms 4916 KB Output is correct
2 Correct 28 ms 5020 KB Output is correct
3 Correct 28 ms 4956 KB Output is correct
4 Correct 29 ms 5004 KB Output is correct
5 Correct 27 ms 4924 KB Output is correct
6 Correct 34 ms 4936 KB Output is correct
7 Correct 36 ms 4924 KB Output is correct
8 Correct 27 ms 4924 KB Output is correct
9 Correct 37 ms 4916 KB Output is correct
10 Correct 44 ms 4924 KB Output is correct
11 Correct 36 ms 4784 KB Output is correct
12 Correct 70 ms 6964 KB Output is correct
13 Correct 105 ms 9272 KB Output is correct
14 Correct 167 ms 11584 KB Output is correct
15 Correct 177 ms 13876 KB Output is correct
16 Correct 224 ms 16176 KB Output is correct
17 Correct 282 ms 18364 KB Output is correct
18 Correct 327 ms 20740 KB Output is correct
19 Correct 336 ms 23228 KB Output is correct
20 Correct 266 ms 18420 KB Output is correct