Submission #674296

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
674296	2022-12-23T16:38:20 Z	thienbao1602	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	423 ms	26416 KB

jobs

#include    <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
using namespace std;

int N, D, M;
vector<pair<int, int>> jobs;

pair<bool, vector<vi>> check(const vector<pair<int, int>> &jobs, int machine)
{
    vector<vi> schedule(N);
    int id_job = 0;
    for(int i=1; i<=N; i++)
    {
        for(int cur_machine=0; cur_machine<machine; cur_machine++)
        {
            if (jobs[id_job].fi > i) break;

            if (jobs[id_job].fi + D >= i)
            {
                schedule[i - 1].pb(jobs[id_job++].se);
            } else return make_pair(false, schedule);

            if (id_job == M) return make_pair(true, schedule);
        }
    }
    return make_pair(false, schedule);
}

void solve()
{
    cin >> N >> D >> M;
    vector<pair<int, int>> jobs(M);
    for(int i=0; i<M; i++)
    {
        int x;
        cin >> x;
        jobs[i] = make_pair(x, i + 1);
    }

    sort(jobs.begin(), jobs.end());

    vector<vi> ans;
    int l = 1, r = M;
    while(l < r)
    {
        int m = (l + r) >> 1;
        pair<bool, vector<vi>> curResult = check(jobs, m);
        if (curResult.fi)
        {
            r = m;
            ans = curResult.se;
        } else
        {
            l = m + 1;
        }
    }

    cout << l << "\n";
    for(int i=0; i<N; i++)
    {
        for(int &idx : ans[i])
        {
            cout << idx << " ";
        }
        cout << 0 << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	2976 KB	Output is correct
2	Correct	30 ms	3012 KB	Output is correct
3	Correct	30 ms	2976 KB	Output is correct
4	Correct	30 ms	2980 KB	Output is correct
5	Correct	29 ms	3084 KB	Output is correct
6	Correct	30 ms	3004 KB	Output is correct
7	Correct	34 ms	3100 KB	Output is correct
8	Correct	45 ms	3028 KB	Output is correct
9	Correct	76 ms	9672 KB	Output is correct
10	Correct	79 ms	9720 KB	Output is correct
11	Correct	38 ms	2780 KB	Output is correct
12	Correct	77 ms	4972 KB	Output is correct
13	Correct	117 ms	8512 KB	Output is correct
14	Correct	187 ms	10780 KB	Output is correct
15	Correct	204 ms	10916 KB	Output is correct
16	Correct	277 ms	16132 KB	Output is correct
17	Correct	334 ms	18820 KB	Output is correct
18	Correct	336 ms	23164 KB	Output is correct
19	Correct	423 ms	26416 KB	Output is correct
20	Correct	348 ms	18780 KB	Output is correct