Submission #1207376

#TimeUsernameProblemLanguageResultExecution timeMemory
1207376spetrJob Scheduling (CEOI12_jobs)C++20
100 / 100
188 ms8624 KiB
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vl vector<long long>
#define vll vector<vector<long long>>

bool solve(ll n, ll d, vl& cisla){
    ll day = 0;
    ll ukazatel = 0;
    queue<ll> fronta;
    while (ukazatel < cisla.size() || !fronta.empty()){
        if (ukazatel < cisla.size()){
            while (cisla[ukazatel] <= day){
                fronta.push(cisla[ukazatel]);
                ukazatel ++;
                if (ukazatel >= cisla.size()){
                    break;
                }
            }
        }


        for (ll i = 0; i < n; i++){
            if (fronta.size()>0){
                ll prvek = fronta.front();
                fronta.pop();
                if (prvek + d < day){
                    return false;
                }
            }
            else{
                break;
            }
        }

        day++;

    }
    return true;
}

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

    ll n, d, m;
    cin >> n >> d >> m;

    vl cisla;
    for (ll i = 0; i < m; i++){
        ll a;
        cin >> a;
        cisla.push_back(a);
    }

    sort(cisla.begin(), cisla.end());

    ll r = m+1;
    ll l = 0;
    ll mid = (l+r+1)/2;
    while (!(solve(mid, d, cisla) == true && solve(mid-1, d, cisla) == false)){
        bool pokus = solve(mid, d, cisla);
        if (pokus == false){
            l = mid+1;
        }
        else{
            r = mid;
        }

        mid = (l+r)/2;
    }
    cout << mid << "\n";
    for (ll i = 0; i < n; i++){
        cout << 0 << "\n";
    }
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...