Submission #565638

#	Time	Username	Problem	Language	Result	Execution time	Memory
565638		PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	496 ms	35836 KiB

jobs

#include <bits/stdc++.h>
#include <limits.h>
#define ll long long
#define ull unsigned long long
#define INF 1000000007

using namespace std;
ll n, d, t;
vector<pair<ll, ll>> dates;
vector<vector<ll>> ans;
bool ok(ll x)
{
    ans.clear();
    ll machines = 1;
    ll day = 1;
    vector<ll> tmp;
    for (ll i = 1; i <= t; i++)
    {
        if (day - dates[i].first > d)
            return 0;
        if (day < dates[i].first)
        {
            day = dates[i].first;
            machines = 1;
        }
        ++machines;
        tmp.push_back(dates[i].second);
        if (machines > x)
        {
            ans.push_back(tmp);
            tmp.clear();
            machines = 1;

            ++day;
        }
    }
    return true;
}
int main()
{
    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 = t;
    while (r > l + 1)
    {
        ll m = l + (r - l) / 2;
        if (ok(m))
            r = m;
        else
            l = m;
    }
    cout << r << "\n";
    for (auto v : ans)
    {
        for (auto e : v)
        {
            cout << e << " ";
        }
        cout << "0\n";
    }
    for (ll i = 1; i <= n - ans.size(); ++i)
        cout << 0 << "\n";

    return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   69 |     for (ll i = 1; i <= n - ans.size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100