Submission #1015024

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015024	2024-07-06T01:55:04 Z	aufan	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	187 ms	34640 KB

jobs

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, d, m;
        cin >> n >> d >> m;

        vector<int> a(m);
        for (int i = 0; i < m; i++) cin >> a[i];

        vector<int> ord(m);
        iota(ord.begin(), ord.end(), 0);
        sort(ord.begin(), ord.end(), [&](int x, int y) {
                return a[x] < a[y];
        });

        int lf = 1, rg = m, ans = -1;
        while (lf <= rg) {
                int md = (lf + rg) / 2;

                int p = 1, c = 0, ok = 1;
                for (int i = 0; i < m; i++) {
                        while (p < a[ord[i]]) {
                                p += 1;
                                c = 0;
                        }

                        if (c == md) {
                                p += 1;
                                c = 0;
                        }

                        if (p > a[ord[i]] + d) {
                                ok = 0;
                                break;
                        }

                        c += 1;
                }

                if (ok && p <= n) {
                        ans = md;
                        rg = md - 1;
                } else {
                        lf = md + 1;
                }
        }

        int p = 1, c = 0;
        vector<vector<int>> v(n + 1);
        for (int i = 0; i < m; i++) {
                while (p < a[ord[i]]) {
                        p += 1;
                        c = 0;
                }

                if (c == ans) {
                        p += 1;
                        c = 0;
                }

                v[p].push_back(ord[i]);
                c += 1;
        }

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

Subtask #1

95.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	3932 KB	Output is correct
2	Correct	13 ms	3868 KB	Output is correct
3	Correct	13 ms	3932 KB	Output is correct
4	Correct	13 ms	3932 KB	Output is correct
5	Correct	13 ms	3936 KB	Output is correct
6	Correct	13 ms	3932 KB	Output is correct
7	Correct	14 ms	3864 KB	Output is correct
8	Correct	12 ms	3936 KB	Output is correct
9	Correct	20 ms	6120 KB	Output is correct
10	Correct	22 ms	6228 KB	Output is correct
11	Correct	17 ms	3928 KB	Output is correct
12	Correct	38 ms	7672 KB	Output is correct
13	Correct	58 ms	12116 KB	Output is correct
14	Correct	83 ms	16724 KB	Output is correct
15	Correct	99 ms	17528 KB	Output is correct
16	Correct	131 ms	22184 KB	Output is correct
17	Correct	160 ms	29384 KB	Output is correct
18	Correct	180 ms	29780 KB	Output is correct
19	Runtime error	187 ms	34640 KB	Memory limit exceeded
20	Correct	175 ms	29616 KB	Output is correct