Submission #565653

#	Time	Username	Problem	Language	Result	Execution time	Memory
565653		PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	1099 ms	58424 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 (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:74:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   74 |     for (ll i = 1; i <= n - ans.size(); ++i)
      |                    ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100