Submission #1280906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280906		SSKMF	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	173 ms	13884 KiB

jobs

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

pair <int , int> moment[1000001];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int durata , termen , lungime;
    cin >> durata >> termen >> lungime;

    for (int indice = 0 ; indice < lungime ; indice++)
        { cin >> moment[indice].first; moment[indice].second = indice + 1; }
    
    sort(moment , moment + lungime);

    int stanga = 1 , dreapta = lungime;
    while (stanga <= dreapta)
    {
        bool gasit = false;
        const int candidat = (stanga + dreapta) >> 1;
        for (int indice = 0 , adaugat = 0 , __moment = 1 ; indice < lungime ; indice++)
        {
            if (moment[indice].first > __moment)
                { __moment = moment[indice].first; adaugat = 0; }

            if (moment[indice].first + termen < __moment)
                { gasit = true; break; }

            if (++adaugat == candidat)
                { __moment++; adaugat = 0; }
        }

        if (gasit) { stanga = candidat + 1; }
        else { dreapta = candidat - 1; }
    }
    
    cout << stanga << '\n';

    for (int indice = 1 , __indice = 0 ; indice <= durata ; indice++)
    {
        for (int ramas = stanga ; ramas && __indice < lungime && moment[__indice].first <= indice ; ramas-- , __indice++)
            { cout << moment[__indice].second << ' '; }

        cout << "0\n";
    }

    return 0;
}

• Subtask 1: 100 / 100