Submission #785699

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785699	2023-07-17T13:20:08 Z	raphaelp	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	291 ms	14000 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;
            }
        }
    }
    while (Jcount[j] == 0 && j < Jcount.size())
    {
        j++;
    }
    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:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (Jcount[j] == 0 && j < Jcount.size())
      |                              ~~^~~~~~~~~~~~~~~
jobs.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     if (j < Jcount.size())
      |         ~~^~~~~~~~~~~~~~~
jobs.cpp: In function 'int dico(int, int, std::vector<int>&, int)':
jobs.cpp:39:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   39 |     if (mil == left)
      |        ^
jobs.cpp: In function 'int main()':
jobs.cpp:67:16: warning: unused variable 'b' [-Wunused-variable]
   67 |     int j = 0, b = 0;
      |                ^

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	1612 KB	Output is correct
2	Correct	29 ms	1700 KB	Output is correct
3	Correct	29 ms	1604 KB	Output is correct
4	Correct	29 ms	1696 KB	Output is correct
5	Correct	29 ms	1684 KB	Output is correct
6	Correct	29 ms	1604 KB	Output is correct
7	Correct	29 ms	1660 KB	Output is correct
8	Correct	30 ms	1692 KB	Output is correct
9	Correct	119 ms	4484 KB	Output is correct
10	Correct	129 ms	4420 KB	Output is correct
11	Correct	23 ms	1400 KB	Output is correct
12	Correct	43 ms	2612 KB	Output is correct
13	Correct	64 ms	4484 KB	Output is correct
14	Correct	113 ms	5868 KB	Output is correct
15	Correct	105 ms	6752 KB	Output is correct
16	Correct	172 ms	8568 KB	Output is correct
17	Correct	233 ms	10548 KB	Output is correct
18	Correct	181 ms	10552 KB	Output is correct
19	Correct	291 ms	14000 KB	Output is correct
20	Correct	190 ms	10492 KB	Output is correct