Submission #743121

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743121	2023-05-17T08:13:12 Z	Joo	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	304 ms	20164 KB

jobs

#include <bits/stdc++.h>
using namespace std;

int n, D, M;
vector<pair<int, int>> vec;
vector<vector<int>> ansDetail;

bool chk(int mid)
{
    int ptr = 0;
    for (int day = 1; day <= n; day++)
    {
        ansDetail[day].clear();
        if (ptr >= M)
            continue;
        for (int i = 1; i <= mid and ptr < M; i++)
        {
            if (day > vec[ptr].first + D)
                return false;

            if (day >= vec[ptr].first)
            {
                ansDetail[day].emplace_back(vec[ptr].second);
                ptr++;
            }

            if (ptr >= M or day < vec[ptr].first)
            {
                break;
            }
        }
    }
    return true;
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> D >> M;
    ansDetail.resize(n + 1);
    for (int i = 1; i <= M; i++)
    {
        int x;
        cin >> x;
        vec.emplace_back(x, i);
    }

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

    int l = 1, r = M, ans = -1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (chk(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout << ans << "\n";
    for (int i = 1; i <= n; i++)
    {
        for (int v : ansDetail[i])
        {
            cout << v << " ";
        }
        cout << "0\n";
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2592 KB	Output is correct
2	Correct	34 ms	2528 KB	Output is correct
3	Correct	25 ms	2508 KB	Output is correct
4	Correct	23 ms	2512 KB	Output is correct
5	Correct	28 ms	2512 KB	Output is correct
6	Correct	25 ms	2560 KB	Output is correct
7	Correct	28 ms	2512 KB	Output is correct
8	Correct	30 ms	2512 KB	Output is correct
9	Correct	34 ms	4684 KB	Output is correct
10	Correct	34 ms	4808 KB	Output is correct
11	Correct	31 ms	2164 KB	Output is correct
12	Correct	64 ms	4216 KB	Output is correct
13	Correct	105 ms	6652 KB	Output is correct
14	Correct	150 ms	9064 KB	Output is correct
15	Correct	166 ms	10548 KB	Output is correct
16	Correct	206 ms	12800 KB	Output is correct
17	Correct	247 ms	16332 KB	Output is correct
18	Correct	272 ms	16400 KB	Output is correct
19	Correct	304 ms	20164 KB	Output is correct
20	Correct	262 ms	16376 KB	Output is correct