Submission #1275295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275295		m_a_d	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	282 ms	20896 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define int long long

bool check(vector<pair<int, int>>& jobs, int machine_a, int d, int n) {
    int jobs_ptr=0;
    for(int i=0; i<n; ++i) {
        if(jobs_ptr==jobs.size()) return 1;
        if(i>jobs[jobs_ptr].first+d) return 0;
        int available=machine_a;
        while(available>0 && jobs_ptr<jobs.size() && jobs[jobs_ptr].first<=i) {
            available--;
            jobs_ptr++;
        }
        if(jobs_ptr==jobs.size()) return 1;
        if(i>jobs[jobs_ptr].first+d) return 0;
    }
    cout << jobs_ptr;
    return 0;
}

int32_t main() {
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> jobs(m);
    for(int i=0; i<m; ++i) cin >> jobs[i].first, jobs[i].first--, jobs[i].second=i;
    sort(jobs.begin(), jobs.end());
    int lo=1, hi=m;
    int mid;
    while(lo<hi) {
        mid=lo+(hi-lo)/2;
        if(check(jobs, mid, d, n)) {
            hi=mid;
        }
        else {
            lo=mid+1;
        }
    }
    cout << hi << "\n";
    int jobs_ptr=0;
    for(int i=0; i<n; ++i) {
        int available=hi;
        while(available>0 && jobs_ptr<jobs.size() && jobs[jobs_ptr].first<=i) {
            available--;
            cout << jobs[jobs_ptr].second+1 << " ";
            jobs_ptr++;
        }
        cout << 0 << "\n";
    }
    return 0;
}

• Subtask 1: 100 / 100