Submission #565542

#	Time	Username	Problem	Language	Result	Execution time	Memory
565542		PranjalChandra	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	535 ms	59304 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
#define ld long double
int const M = 1e6 + 10, M2 = 1e7 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int m, d, a[M], n;
vector<int> hlp[M];
vector<pii> all;
bool check(int x, bool ch)
{
    int day = 1, cnt = 0;
    for (int i = 0; i < m; i++)
    {
        if (cnt == x)
            day++, cnt = 0;
        if (day > n)
            return 0;
        //if job to be done is later than day must be == that day
        if (day < all[i].F)
            day = all[i].F, cnt = 0;
        if (day > all[i].F + d)
            return 0;
        if (ch)
            hlp[day].pb(all[i].S);
        cnt++;
    }
    return 1;
}
int32_t main()
{
    cin >> n >> d >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        all.pb(mp(a[i], i));
    }
    sort(all.begin(), all.end());
    int lo = 0, hi = m;
    while (hi > lo + 1)
    {
        int mid = (lo + hi) / 2;
        if (check(mid, 0))
            hi = mid;
        else
            lo = mid ;
    }
    int ans = hi;
   // if (check(lo, 0))
      //  ans = lo;
    check(ans, 1);
    cout << ans << endl;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < hlp[i].size(); j++)
            cout << hlp[i][j] << " ";
        cout << 0 << endl;
    }
}

Compilation message (stderr)

jobs.cpp: In function 'int32_t main()':
jobs.cpp:60:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j = 0; j < hlp[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
jobs.cpp:57:9: warning: unused variable 'cnt' [-Wunused-variable]
   57 |     int cnt = 0;
      |         ^~~

• Subtask 1: 60 / 100