Submission #960448

#	Time	Username	Problem	Language	Result	Execution time	Memory
960448		Nelt	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	155 ms	27452 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

void solve()
{
    ll n, d, m;
    cin >> n >> d >> m;
    vector<ll> v[n + 1];
    ll tm[m + 1];
    for (ll i = 1; i <= m; i++)
    {
        cin >> tm[i];
        v[tm[i]].push_back(i);
    }
    ll l = 1, r = m;
    queue<ll> q;
    vector<ll> ans[n + 1];
    while (l <= r)
    {
        ll mid = (l + r) >> 1;
        bool ok = true;
        while (!q.empty())
            q.pop();
        for (ll i = 1, cnt; i <= n; i++)
        {
            for (ll j : v[i])
                q.push(j);
            if (!q.empty() and tm[q.front()] + d < i)
            {
                ok = false;
                break;
            }
            cnt = 0;
            while (!q.empty() and cnt < mid)
                cnt++, q.pop();
        }
        if (ok)
            r = mid - 1;
        else
            l = mid + 1;
    }
    cout << ++r << endl;
    while (!q.empty())
        q.pop();
    for (ll i = 1, cnt; i <= n; i++)
    {
        for (ll j : v[i])
            q.push(j);
        cnt = 0;
        while (!q.empty() and cnt < r)
            cout << q.front() << " ", cnt++, q.pop();
        cout << "0\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

• Subtask 1: 100 / 100