Submission #528700

#	Time	Username	Problem	Language	Result	Execution time	Memory
528700		Aanjaney	Job Scheduling (CEOI12_jobs)	C++17	80 / 100	595 ms	45432 KiB

jobs

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define MODA 998244353
#define pb push_back
#define mp make_pair
#define sortv(v) sort(v.begin(), v.end())
#define sorta(A, N) sort(A, A + N)
#define debug(x) cerr << #x << " is " << x;
#define rep(i, a, N) for (ll i = a; i < N; i++)
#define f first
#define s second
#define uniq(v)                                       \
    {                                                 \
        sort(v.begin(), v.end());                     \
        v.erase(unique(v.begin(), v.end()), v.end()); \
    }
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;
ll N, D, M;
pair<bool, vector<vector<ll> > > isFeasible(const vector<pair<ll, ll> > &jobs, int machineCount)
{
    vector<vector<ll> > schedule(N);
    ll reqNum = 0;
    rep(day, 1, N + 1)
    {
        rep(j, 0, machineCount)
        {
            if (jobs[reqNum].first > day)
                break;

            if (jobs[reqNum].first + D >= day)
                schedule[day - 1].push_back(jobs[reqNum++].second);

            else
                return mp(false, schedule);

            if (reqNum == M)
                return mp(true, schedule);
        }
    }

    return mp(false, schedule);
}

void solve(ll tcase)
{
    cin >> N >> D >> M;
    vector<pair<ll, ll> > jobs(M);
    rep(i, 0, M)
    {
        ll day;
        cin >> day;
        jobs[i] = mp(day, i + 1);
    }
    sortv(jobs);

    vector<vector<ll> > result;
    ll l = 1, r = M;
    while (l < r)
    {
        ll machineNum = (l + r) / 2;
        pair<bool, vector<vector<ll> > > curResult = isFeasible(jobs, machineNum);
        if (curResult.first)
        {
            r = machineNum;
            result = curResult.second;
        }
        else
            l = machineNum + 1;
    }

    cout << l << "\n";
    rep(i, 0, N)
    {
        for (ll &idx : result[i])
            cout << idx << " ";
        cout << 0 << "\n";
    }
}
int main()
{

    speed;
    ll t = 1;
    rep(i, 1, t + 1)
        solve(i);
}

• Subtask 1: 80 / 100