Submission #757283

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757283	2023-06-13T01:45:55 Z	yash_9a3b	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	490 ms	21988 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	4988 KB	Output is correct
2	Correct	42 ms	4884 KB	Output is correct
3	Correct	45 ms	4980 KB	Output is correct
4	Correct	44 ms	4996 KB	Output is correct
5	Correct	41 ms	4928 KB	Output is correct
6	Correct	43 ms	4948 KB	Output is correct
7	Correct	42 ms	4980 KB	Output is correct
8	Correct	42 ms	4984 KB	Output is correct
9	Correct	167 ms	4928 KB	Output is correct
10	Correct	154 ms	4972 KB	Output is correct
11	Correct	44 ms	4852 KB	Output is correct
12	Correct	85 ms	7248 KB	Output is correct
13	Correct	155 ms	10080 KB	Output is correct
14	Correct	189 ms	13068 KB	Output is correct
15	Correct	202 ms	13748 KB	Output is correct
16	Correct	300 ms	15852 KB	Output is correct
17	Correct	321 ms	19700 KB	Output is correct
18	Correct	345 ms	19988 KB	Output is correct
19	Correct	490 ms	21988 KB	Output is correct
20	Correct	335 ms	19444 KB	Output is correct