Submission #743127

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743127	2023-05-17T08:14:48 Z	Joo	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	315 ms	20272 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();
        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	38 ms	2892 KB	Output is correct
2	Correct	28 ms	2812 KB	Output is correct
3	Correct	27 ms	2812 KB	Output is correct
4	Correct	25 ms	2816 KB	Output is correct
5	Correct	25 ms	2804 KB	Output is correct
6	Correct	25 ms	2888 KB	Output is correct
7	Correct	26 ms	2888 KB	Output is correct
8	Correct	35 ms	2884 KB	Output is correct
9	Correct	46 ms	5072 KB	Output is correct
10	Correct	74 ms	5060 KB	Output is correct
11	Correct	33 ms	2500 KB	Output is correct
12	Correct	88 ms	4532 KB	Output is correct
13	Correct	103 ms	6908 KB	Output is correct
14	Correct	148 ms	9300 KB	Output is correct
15	Correct	174 ms	11060 KB	Output is correct
16	Correct	217 ms	13200 KB	Output is correct
17	Correct	248 ms	16860 KB	Output is correct
18	Correct	282 ms	16756 KB	Output is correct
19	Correct	315 ms	20272 KB	Output is correct
20	Correct	233 ms	16324 KB	Output is correct