제출 #674261

#제출 시각아이디문제언어결과실행 시간메모리
674261thienbao1602Job Scheduling (CEOI12_jobs)C++17
0 / 100
219 ms20924 KiB
#include    <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;

int days, delay, number_jobs;
vector<pair<ll, ll>> jobs;

bool check(ll machine)
{
    ll cur_jobs = 0, cur_days = 1;
    for(int i=0; i<number_jobs; i++)
    {
        if (jobs[i].fi <= cur_days + delay)
        {
            cur_jobs++;
        } else return false;

        if (cur_jobs == machine)
        {
            cur_days++, cur_jobs = 0;
        }
    }
    return (cur_days <= days);
}

ll bs(ll l, ll r)
{
    while(l < r)
    {
        ll m = (l + r) >> 1;
        if (check(m))
        {
            r = m;
        } else
        {
            l = m + 1;
        }
    }
    return l;
}

void solve()
{
    cin >> days >> delay >> number_jobs;
    for(int i=0; i<number_jobs; i++)
    {
        ll x;
        cin >> x;
        jobs.push_back({x, i + 1});
    }

    sort(jobs.begin(), jobs.end());
    ll ret = bs(1, days + 1);

    cout << ret << "\n";
    int cur = 0, nowDay = days;
    for(int i=0; i<number_jobs; i++)
    {
        cout << jobs[i].se << " ";
        cur++;
        if (cur == ret)
        {
            cur = 0, nowDay--;
            cout << "0\n";
        }
    }

    for(; nowDay>0; nowDay--)
    {
        cout << "0\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...