Submission #1218538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218538		jacobdoesntcode	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	316 ms	26348 KiB

jobs

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> x;
    int a;
    for (int i = 0; i < m; i++){
        cin >> a;
        x.push_back({a, i + 1});
    }
    sort(x.begin(), x.end());
    vector<int> indexes;
    vector<int> jobs;
    for (int i = 0; i < m; i++){
        jobs.push_back(x[i].first);
        indexes.push_back(x[i].second);
    }
    int l = 0;
    int r = m;
    int last_index;
    vector<int> index_records;
    vector<int> best_index_records;
    int ans = m;
    while (l < r){
        int k = (l + r) / 2;
        last_index = 0;
        index_records.clear();
        bool possible = true;
        int day = 1;
        while (last_index < m){
            if (day != 1){
                if (day > jobs[last_index] + d){
                    possible = false;
                    break;
                }
            }
            last_index = min(last_index + k, (int)(upper_bound(jobs.begin(), jobs.end(), day) - jobs.begin()));
            index_records.push_back(last_index);
            day++;
        }
        if (possible){
            r = k;
            ans = min(ans, k);
            best_index_records = index_records;
        }
        else{
            l = k + 1;
        }
    }
    cout << ans << endl;
    int count = 0;
    int curr_idx = 0;
    int prints = 1;
    for (int i = 0; i < indexes.size(); i++){
        if (count >= ans or i > best_index_records[curr_idx]){
            cout << 0 << endl << indexes[i] << " ";
            count = 1;
            curr_idx++;
            prints++;
        }
        else{
            cout << indexes[i] << " ";
            count++;
        }
    }
    cout << 0 << endl;
    for (int i = 0; i < n - prints; i++){
        cout << 0 << endl;
    }
}

• Subtask 1: 100 / 100