제출 #708526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708526		jsathu07	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	293 ms	27888 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

bool calc(ll n, ll d, ll x, vector<ll> &arr, ll m)
{
    ll j = 0;
    bool p = true;
    for (ll i = 0; i < n; i++)
    {
        ll y = x;
        while (y-- && j < m)
        {
            if (!(i + 1 <= arr[j] + d))
            {
                p = false;
                break;
            }
            // cout << "day " << i + 1 << " processed " << j + 1 << " \n";
            j++;
        }
        if (!p)
            break;
    }
    return p;
}

void solve()
{
    ll n, d, m;
    cin >> n >> d >> m;
    vector<ll> arr(m, 0);
    vector<pair<ll, ll>> brr;
    for (ll i = 0; i < m; i++)
    {
        cin >> arr[i];
        brr.push_back({arr[i], i + 1});
    }
    sort(brr.begin(), brr.end());
    sort(arr.begin(), arr.end());
    ll l = 1, r = 1e15, ans = 1e6;
    while (l <= r)
    {
        ll mid = (l + r) / 2;
        if (calc(n, d, mid, arr, m))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << ans << "\n";
    ll k = 0, rem = 0;
    for (auto &i : brr)
    {
        if (k == ans)
        {
            cout << 0 << "\n";
            k = 0;
            rem++;
        }
        cout << i.second << " ";
        k++;
    }
    rem++;
    cout << 0 << "\n";
    ll q = n - rem;
    while (q > 0)
    {
        cout << 0 << "\n";
        q--;
    }
}

// void setIO(string s)
// {
//     freopen((s + ".in").c_str(), "r", stdin);
//     freopen((s + ".out").c_str(), "w", stdout);
// }

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

• Subtask 1: 55 / 100