Submission #674260

#	Time	Username	Problem	Language	Result	Execution time	Memory
674260		thienbao1602	Job Scheduling (CEOI12_jobs)	C++17	25 / 100	236 ms	22976 KiB

jobs

#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++;
        }

        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;
}

• Subtask 1: 25 / 100