Submission #743118

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743118	2023-05-17T08:11:58 Z	Joo	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	323 ms	20224 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; i++)
        {
            if (ptr < M and day > vec[ptr].first + D)
                return false;

            if (ptr < M and day >= vec[ptr].first)
            {
                ansDetail[day].emplace_back(vec[ptr].second);
                ptr++;
            }
            else 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	26 ms	2504 KB	Output is correct
2	Correct	24 ms	2528 KB	Output is correct
3	Correct	27 ms	2504 KB	Output is correct
4	Correct	25 ms	2524 KB	Output is correct
5	Correct	29 ms	2512 KB	Output is correct
6	Correct	26 ms	2512 KB	Output is correct
7	Correct	25 ms	2524 KB	Output is correct
8	Correct	24 ms	2572 KB	Output is correct
9	Correct	37 ms	4744 KB	Output is correct
10	Correct	34 ms	4780 KB	Output is correct
11	Correct	31 ms	2164 KB	Output is correct
12	Correct	78 ms	4144 KB	Output is correct
13	Correct	97 ms	6656 KB	Output is correct
14	Correct	140 ms	9024 KB	Output is correct
15	Correct	155 ms	10568 KB	Output is correct
16	Correct	212 ms	12720 KB	Output is correct
17	Correct	245 ms	16332 KB	Output is correct
18	Correct	294 ms	16452 KB	Output is correct
19	Correct	323 ms	20224 KB	Output is correct
20	Correct	231 ms	16304 KB	Output is correct