Submission #1015025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015025	2024-07-06T01:55:31 Z	aufan	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	194 ms	20112 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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	2396 KB	Output is correct
2	Correct	11 ms	2392 KB	Output is correct
3	Correct	11 ms	2396 KB	Output is correct
4	Correct	11 ms	2392 KB	Output is correct
5	Correct	12 ms	2396 KB	Output is correct
6	Correct	12 ms	2392 KB	Output is correct
7	Correct	13 ms	2392 KB	Output is correct
8	Correct	12 ms	2528 KB	Output is correct
9	Correct	20 ms	4700 KB	Output is correct
10	Correct	25 ms	4740 KB	Output is correct
11	Correct	16 ms	2136 KB	Output is correct
12	Correct	37 ms	4316 KB	Output is correct
13	Correct	56 ms	6736 KB	Output is correct
14	Correct	81 ms	9040 KB	Output is correct
15	Correct	99 ms	9812 KB	Output is correct
16	Correct	116 ms	12040 KB	Output is correct
17	Correct	137 ms	15912 KB	Output is correct
18	Correct	194 ms	16376 KB	Output is correct
19	Correct	186 ms	20112 KB	Output is correct
20	Correct	152 ms	15960 KB	Output is correct