Submission #874534

#	Time	Username	Problem	Language	Result	Execution time	Memory
874534		vjudge1	Job Scheduling (CEOI12_jobs)	C++14	55 / 100	181 ms	21332 KiB

jobs

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdint>

using namespace std;
using Pair = pair<int64_t, int64_t>;

constexpr int64_t maxn = 1000000;
int64_t n, d, m;
Pair a[maxn];

int main()
{
    ios_base::sync_with_stdio(false);

    cin >> n >> d >> m;
    for (int64_t i = 0; i < m; i++)
    {
        cin >> a[i].first;
        a[i].second = i + 1;
    }
    sort(a, a + m);

    int64_t l = 1, r = m;
    while (l < r)
    {
        int64_t k = (l + r) / 2;

        bool result = true;
        for (int64_t i = 0; i * k < m; i++)
        {
            if (i >= a[i * k].first + d || i >= n)
            {
                result = false;
                break;
            }
        }

        if (result)
            r = k;
        else
            l = k + 1;
    }

    cout << r << '\n';
    for (int64_t i = 0; i < n; i++)
    {
        for (int64_t j = i * r; j < min(m, (i + 1) * r); j++)
            cout << a[j].second << ' ';
        cout << "0\n";
    }

    return 0;
}

• Subtask 1: 55 / 100