Submission #1207370

#TimeUsernameProblemLanguageResultExecution timeMemory
1207370spetrJob Scheduling (CEOI12_jobs)C++20
5 / 100
1098 ms8656 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()){
        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;
                }
            }
        }

        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;
    ll l = 0;
    ll mid = (l+r)/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 - 1;
        }

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