Submission #729678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
729678	2023-04-24T10:45:45 Z	PanosPask	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	153 ms	17652 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int n ,d, m;
vector<int> jobs;
vector<vector<int>> job_ids;

bool can_complete(int x)
{
    int cur_day = 0;
    vector<int> jobs_at = jobs;
    for (int i = 0; i < n; i++) {
        if (i - cur_day > d)
            return false;

        int avail = x;
        while (avail > 0 && cur_day <= i) {
            int rm = min(avail, jobs_at[cur_day]);
            avail -= rm;
            jobs_at[cur_day] -= rm;
            while (cur_day <= i && jobs_at[cur_day] == 0)
                cur_day++;
        }
    }

    return true;
}

int main(void)
{
    scanf("%d %d %d", &n, &d, &m);
    jobs.assign(n, 0);
    job_ids.resize(n);
    for (int i = 0; i < m; i++) {
        int day;
        scanf("%d", &day);
        day--;

        jobs[day]++;
        job_ids[day].push_back(i + 1);
    }

    int l = 0;
    int r = m;
    while (r > l + 1) {
        int mid = (l + r) / 2;
        if (can_complete(mid))
            r = mid;
        else
            l = mid;
    }

    printf("%d\n", r);
    int cur_day = 0;
    for (int i = 0; i < n; i++) {
        int rem = r;
        while (cur_day <= i && rem !=  0) {
            int proc = min(rem, (int)job_ids[cur_day].size());
            for (int i = 0; i < proc; i++) {
                printf("%d ", job_ids[cur_day].back());
                job_ids[cur_day].pop_back();
            }
            rem -= proc;

            while (cur_day <= i && job_ids[cur_day].size() == 0)
                cur_day++;
        }

        printf("0\n");
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d %d %d", &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jobs.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d", &day);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	1996 KB	Output is correct
2	Correct	16 ms	1996 KB	Output is correct
3	Correct	18 ms	1904 KB	Output is correct
4	Correct	20 ms	1968 KB	Output is correct
5	Correct	19 ms	1964 KB	Output is correct
6	Correct	16 ms	1996 KB	Output is correct
7	Correct	16 ms	1968 KB	Output is correct
8	Correct	16 ms	2000 KB	Output is correct
9	Correct	23 ms	5068 KB	Output is correct
10	Correct	23 ms	5044 KB	Output is correct
11	Correct	19 ms	1876 KB	Output is correct
12	Correct	34 ms	3300 KB	Output is correct
13	Correct	50 ms	5668 KB	Output is correct
14	Correct	82 ms	7804 KB	Output is correct
15	Correct	82 ms	8540 KB	Output is correct
16	Correct	128 ms	11500 KB	Output is correct
17	Correct	137 ms	13864 KB	Output is correct
18	Correct	139 ms	13560 KB	Output is correct
19	Correct	153 ms	17652 KB	Output is correct
20	Correct	141 ms	13820 KB	Output is correct