Submission #752757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
752757	2023-06-03T16:45:21 Z	Mo_Huzaifa	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	498 ms	20056 KB

jobs

#include <bits/stdc++.h>
using namespace std;

using i64 = int;
i64 const &N_ = 1e5 + 1; 
i64 const &M_ = 1e6 + 1;

i64 N, D, M;
vector < i64 > ans[N_];
vector < pair < i64, i64 >> DAYS;

bool check(i64 machine) {
    i64 d = 0;
    i64 cnt = 0;
    for (i64 i = 0; i < (i64) DAYS.size(); ) {
        i64 j = i;
        bool ok = false;
        i64 val = max(DAYS[i].first, d + 1);
        for (i64 cnt_ = 0; j < M and DAYS[j].first < val + 1 and DAYS[j].first >= val - D and cnt_ < machine; ++ cnt_, ++ j) {
            // Let it be
            cnt ++;
            ok = true;
        }
        if (! ok) return false;
        i = j;
        d = val;
    }
    return cnt == M;
}

void get_ans(i64 machine) {
    i64 d = 0;
    for (i64 i = 0; i < (i64) DAYS.size(); ) {
        i64 j = i;
        bool ok = false;
        i64 val = max(DAYS[i].first, d + 1);
        for (i64 cnt_ = 0; j < M and DAYS[j].first < val + 1 and DAYS[j].first >= val - D and cnt_ < machine; ++ cnt_, ++ j) {
            // Let it be
            ans[val].push_back(DAYS[j].second);
            ok = true;
        }
        if (! ok) return ;
        i = j;
        d = val;
    }
}

void Solution() {
    cin >> N >> D >> M;
    for (i64 i = 0; i < M; ++ i) {
        i64 a;
        cin >> a;
        DAYS.push_back(make_pair(a, i + 1));
    }

    i64 save = -1;
    sort(DAYS.begin(), DAYS.end());

    i64 l = 0, r = M;
    while (l < r + 1) {
        i64 mid = (l + r) / 2;
        if (check(mid)) save = mid, r = mid - 1;
        else l = mid + 1;
    }

    get_ans(save);
    cout << save << endl;
    for (i64 i = 1; i < N + 1; ++ i) {
        for (auto it : ans[i]) {
            cout << it << ' ';
        }
        cout << '0' << endl;
    }
}

int main() {
    Solution();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	4668 KB	Output is correct
2	Correct	47 ms	4584 KB	Output is correct
3	Correct	44 ms	4604 KB	Output is correct
4	Correct	42 ms	4692 KB	Output is correct
5	Correct	43 ms	4628 KB	Output is correct
6	Correct	45 ms	4688 KB	Output is correct
7	Correct	43 ms	4684 KB	Output is correct
8	Correct	44 ms	4732 KB	Output is correct
9	Correct	153 ms	4752 KB	Output is correct
10	Correct	146 ms	4668 KB	Output is correct
11	Correct	41 ms	4520 KB	Output is correct
12	Correct	81 ms	6468 KB	Output is correct
13	Correct	122 ms	8980 KB	Output is correct
14	Correct	206 ms	11164 KB	Output is correct
15	Correct	207 ms	11952 KB	Output is correct
16	Correct	280 ms	14044 KB	Output is correct
17	Correct	340 ms	17988 KB	Output is correct
18	Correct	338 ms	18468 KB	Output is correct
19	Correct	498 ms	20056 KB	Output is correct
20	Correct	325 ms	18156 KB	Output is correct