Submission #784905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
784905	2023-07-16T18:01:21 Z	raphaelp	Job Scheduling (CEOI12_jobs)	C++14	10 / 100	203 ms	21260 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;
            }
        }
    }
    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);
    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 < Jcount.size(); i++)
    {
        int a = nbMach;
        if (jobs[j].empty())
            j++;
        while (a > 0 && j <= i)
        {
            cout << jobs[j][jobs[j].size() - 1] << ' ';
            jobs[j].pop_back();
            a--;
            if (jobs[j].empty())
                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: In function 'int dico(int, int, std::vector<int>&, int)':
jobs.cpp:33:8: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   33 |     if (mil == left)
      |        ^
jobs.cpp: In function 'int main()':
jobs.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < Jcount.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
jobs.cpp:61:16: warning: unused variable 'b' [-Wunused-variable]
   61 |     int j = 0, b = 0;
      |                ^

Subtask #1

10.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	21 ms	2572 KB	Execution killed with signal 11
2	Runtime error	21 ms	2600 KB	Execution killed with signal 11
3	Runtime error	21 ms	2632 KB	Execution killed with signal 11
4	Runtime error	21 ms	2592 KB	Execution killed with signal 11
5	Runtime error	21 ms	2636 KB	Execution killed with signal 11
6	Runtime error	21 ms	2636 KB	Execution killed with signal 11
7	Runtime error	21 ms	2520 KB	Execution killed with signal 11
8	Runtime error	21 ms	2596 KB	Execution killed with signal 11
9	Runtime error	25 ms	7800 KB	Execution killed with signal 11
10	Runtime error	25 ms	7780 KB	Execution killed with signal 11
11	Runtime error	28 ms	2116 KB	Execution killed with signal 11
12	Correct	47 ms	2624 KB	Output is correct
13	Runtime error	68 ms	6920 KB	Execution killed with signal 11
14	Correct	112 ms	5836 KB	Output is correct
15	Runtime error	109 ms	9952 KB	Execution killed with signal 11
16	Runtime error	167 ms	13028 KB	Execution killed with signal 11
17	Runtime error	203 ms	16272 KB	Execution killed with signal 11
18	Runtime error	197 ms	15656 KB	Execution killed with signal 11
19	Runtime error	202 ms	21260 KB	Execution killed with signal 11
20	Runtime error	189 ms	16208 KB	Execution killed with signal 11