Submission #785694

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785694	2023-07-17T13:11:09 Z	raphaelp	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	310 ms	17372 KB

jobs

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

bool pos(int nb, vector<int> &Jcount, int D)
{
    int j = 0, b = 0;
    for (int i = 0; i < Jcount.size(); i++)
    {
        if (i - j > D)
            return false;
        int a = nb;
        while (a > 0 && j <= i)
        {
            if (a >= Jcount[j] - b)
            {
                a -= Jcount[j] - b;
                j++;
                b = 0;
            }
            else
            {
                b += a;
                a = 0;
            }
        }
    }
    if (j < Jcount.size())
        return false;
    return true;
}

int dico(int left, int right, vector<int> &Jcount, int D)
{
    int mil = (left + right) / 2;
    if (mil == left)
        if (pos(mil, Jcount, D))
            return mil;
        else
            return mil + 1;
    if (pos(mil, Jcount, D))
    {
        return dico(left, mil, Jcount, D);
    }
    else
        return dico(mil, right, Jcount, D);
}

int main()
{
    int N, D, M;
    cin >> N >> D >> M;
    vector<vector<int>> jobs(N);
    vector<int> Jcount(N, 0);
    for (int i = 0; i < M; i++)
    {
        int temp;
        cin >> temp;
        Jcount[temp - 1]++;
        jobs[temp - 1].push_back(i + 1);
    }
    int nbMach = dico(1, M + 1, Jcount, D);
    cout << nbMach << endl;
    int j = 0, b = 0;
    for (int i = 0; i < N; i++)
    {
        int a = nbMach;
        while (jobs[j].empty() && j <= i)
            j++;
        while (a > 0 && j <= i)
        {
            cout << jobs[j][jobs[j].size() - 1] << ' ';
            jobs[j].pop_back();
            a--;
            while (jobs[j].empty() && j <= i)
                j++;
        }
        cout << 0 << endl;
    }
}

Compilation message

jobs.cpp: In function 'bool pos(int, std::vector<int>&, int)':
jobs.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < Jcount.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
jobs.cpp:27:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (j < Jcount.size())
      |         ~~^~~~~~~~~~~~~~~
jobs.cpp: In function 'int dico(int, int, std::vector<int>&, int)':
jobs.cpp:35:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   35 |     if (mil == left)
      |        ^
jobs.cpp: In function 'int main()':
jobs.cpp:63:16: warning: unused variable 'b' [-Wunused-variable]
   63 |     int j = 0, b = 0;
      |                ^

Subtask #1

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	1968 KB	Output is correct
2	Correct	31 ms	1892 KB	Output is correct
3	Correct	35 ms	1888 KB	Output is correct
4	Correct	29 ms	1924 KB	Output is correct
5	Correct	30 ms	1996 KB	Output is correct
6	Correct	29 ms	2000 KB	Output is correct
7	Correct	29 ms	1988 KB	Output is correct
8	Correct	29 ms	1992 KB	Output is correct
9	Correct	119 ms	4696 KB	Output is correct
10	Correct	121 ms	4724 KB	Output is correct
11	Correct	23 ms	1804 KB	Output is correct
12	Incorrect	45 ms	3376 KB	Output isn't correct
13	Correct	64 ms	5380 KB	Output is correct
14	Incorrect	114 ms	7760 KB	Output isn't correct
15	Correct	112 ms	7620 KB	Output is correct
16	Correct	157 ms	11464 KB	Output is correct
17	Correct	183 ms	13896 KB	Output is correct
18	Correct	178 ms	13560 KB	Output is correct
19	Correct	310 ms	17372 KB	Output is correct
20	Correct	195 ms	13868 KB	Output is correct