Submission #785021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
785021	2023-07-16T23:24:30 Z	raphaelp	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	210 ms	21228 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;
        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: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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	21 ms	2500 KB	Execution killed with signal 11
2	Runtime error	24 ms	2568 KB	Execution killed with signal 11
3	Runtime error	21 ms	2540 KB	Execution killed with signal 11
4	Runtime error	21 ms	2612 KB	Execution killed with signal 11
5	Runtime error	21 ms	2612 KB	Execution killed with signal 11
6	Runtime error	27 ms	2556 KB	Execution killed with signal 11
7	Runtime error	21 ms	2536 KB	Execution killed with signal 11
8	Runtime error	22 ms	2632 KB	Execution killed with signal 11
9	Runtime error	26 ms	7796 KB	Execution killed with signal 11
10	Runtime error	25 ms	7824 KB	Execution killed with signal 11
11	Runtime error	24 ms	2168 KB	Execution killed with signal 11
12	Runtime error	45 ms	3816 KB	Execution killed with signal 11
13	Runtime error	69 ms	6892 KB	Execution killed with signal 11
14	Runtime error	114 ms	9016 KB	Execution killed with signal 11
15	Runtime error	110 ms	9932 KB	Execution killed with signal 11
16	Runtime error	166 ms	13060 KB	Execution killed with signal 11
17	Runtime error	210 ms	16260 KB	Execution killed with signal 11
18	Runtime error	175 ms	15564 KB	Execution killed with signal 11
19	Runtime error	210 ms	21228 KB	Execution killed with signal 11
20	Runtime error	194 ms	16204 KB	Execution killed with signal 11