Submission #785694

#	Time	Username	Problem	Language	Result	Execution time	Memory
785694		raphaelp	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	310 ms	17372 KiB

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 (stderr)

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 / 100