Submission #565657

#	Time	Username	Problem	Language	Result	Execution time	Memory
565657		PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	95 / 100	433 ms	35884 KiB

jobs

#include <bits/stdc++.h>
#include <limits.h>
#define ll long long
#define ull unsigned long long
#define INF 1000000007
#define fastio()                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
using namespace std;
ll n, d, t;
vector<pair<ll, ll>> dates;
vector<vector<ll>> ans;
bool ok(ll x)
{
    ans = vector<vector<ll>>(n + 1, vector<ll>());
    ll machines = 1;
    ll day = 1;

    for (ll i = 1; i <= t; i++)
    {
        if (day < dates[i].first)
        {
            day = dates[i].first;
            machines = 1;
        }
        if (day - dates[i].first > d)
            return 0;
        ++machines;
        ans[day].push_back(dates[i].second);
        if (machines > x)
        {
            // ans.push_back(tmp);
            // tmp.clear();
            machines = 1;

            ++day;
        }
    }
    return true;
}
int main()
{
    fastio();
    cin >> n >> d >> t;
    dates.push_back({-1, -1});
    for (ll i = 1; i <= t; i++)
    {
        ll x;
        cin >> x;
        dates.push_back({x, i});
    }
    sort(dates.begin(), dates.end());
    ll l = 0;
    ll r = 1e5 + 12;
    while (r > l + 1)
    {
        ll m = l + (r - l) / 2;
        if (ok(m))
            r = m;
        else
            l = m;
    }
    ok(r);
    cout << r << "\n";
    for (int i = 1; i <= n; i++)
    {
        for (auto j : ans[i])
            cout << j << " ";
        cout << 0 << endl;
    }
    return 0;
}

• Subtask 1: 95 / 100