Submission #642989

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642989	2022-09-21T02:26:24 Z	thinhcute	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	229 ms	13728 KB

jobs

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

#define fi first
#define se second

#define MAX 1001000

int n, d, m;
pair<int, int> a[MAX];

bool f(int mid)
{
    for (int i = 1, j = 1; i <= n && j < m; ++i) {
        int cnt = 0;
        while (j < m && cnt < mid && a[j].first <= i && a[j].first + d >= i) {
            ++cnt;
            ++j;
        } 
        if (j <= m && a[j].first + d < i) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].fi;
        a[i].se = i;
    }

    sort(a + 1, a + m + 1);

    int l = 1, r = m, res = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (f(mid)) {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }

    cout << res << endl;
    
    for (int i = 1, j = 1; i <= n; ++i) {
        int cnt = 0;
        while (j <= m && cnt < res && a[j].first <= i && a[j].first + d >= i) {
            cout << a[j].second << " ";
            ++cnt;
            ++j;
        } 
        cout << "0\n";
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1696 KB	Output is correct
2	Correct	23 ms	1600 KB	Output is correct
3	Correct	18 ms	1708 KB	Output is correct
4	Correct	17 ms	1728 KB	Output is correct
5	Correct	16 ms	1620 KB	Output is correct
6	Correct	16 ms	1636 KB	Output is correct
7	Correct	16 ms	1620 KB	Output is correct
8	Correct	16 ms	1620 KB	Output is correct
9	Correct	26 ms	1792 KB	Output is correct
10	Correct	33 ms	1876 KB	Output is correct
11	Correct	23 ms	1620 KB	Output is correct
12	Correct	48 ms	3124 KB	Output is correct
13	Correct	76 ms	4608 KB	Output is correct
14	Correct	127 ms	6160 KB	Output is correct
15	Correct	120 ms	7548 KB	Output is correct
16	Correct	184 ms	9108 KB	Output is correct
17	Correct	179 ms	10524 KB	Output is correct
18	Correct	202 ms	12020 KB	Output is correct
19	Correct	229 ms	13728 KB	Output is correct
20	Correct	173 ms	10572 KB	Output is correct