Submission #1015024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015024		aufan	Job Scheduling (CEOI12_jobs)	C++17	95 / 100	187 ms	34640 KiB

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 / 100