Submission #1281881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281881		peanut	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	165 ms	13880 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
int n, d, m;
pair<int, int> a[1000005];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> d >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a+1, a+1+m);

    int lo = 0, hi = 1e6 + 1;
    while (lo < hi)
    {
        int mid = lo + (hi - lo) / 2;

        int idx = 1;
        bool flag = true;
        for (int i = 1; i <= n; ++i)
        {
            int cnt = 0;
            while (idx <= m && a[idx].first <= i && cnt < mid)
            {
                if (i - a[idx].first > d)
                {
                    flag = false;
                    break;
                }
                ++cnt, ++idx;
            }
            if (!flag) break;
        }

        if (flag && idx >= m) hi = mid;
        else lo = mid + 1;
    }
    if (lo > 1000000)
    {
        cout << -1;
        return 0;
    }
    cout << lo << '\n';
    int idx = 1;
    for (int i = 1; i <= n; ++i)
    {
        int cnt = 0;
        while (idx <= m && a[idx].first <= i && cnt < lo)
        {
            if (i - a[idx].first > d) break;
            cout << a[idx].second << ' ';
            ++cnt, ++idx;
        }
        cout << "0\n";
    }
    return 0;
}

• Subtask 1: 100 / 100