Submission #1015869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015869		rcll	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	378 ms	26504 KiB

jobs

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

int n,d,m;

pair<bool,vector<vector<int>>> check(const vector<pair<int,int>> &jobs,int count) {
    vector<vector<int>> schedule(n);
    int request_num=0;
    for (int day=1; day<=n; day++) {
        for (int j=0; j<count; j++) {
            if (jobs[request_num].first>day) {
                break;
            }
            if (jobs[request_num].first+d>=day) {
                schedule[day-1].push_back(jobs[request_num++].second);
            }
            else {
                return make_pair(false,schedule);
            }
            if (m==request_num) {
                return make_pair(true,schedule);
            }
        }
    }
    return make_pair(false,schedule);
}

int main() {
    cin >> n >> d >> m;
    vector<pair<int,int>> jobs(m);
    for (int i = 0; i < m; i++) {
        int day;
        cin >> day;
        jobs[i] = make_pair(day,i+1);
    }
    sort(jobs.begin(),jobs.end());

    vector<vector<int>> results;
    int lower=1,upper=m;
    while (lower<upper) {
        int machines=(lower+upper)/2;
        pair<bool,vector<vector<int>>> result =check(jobs,machines);
        if (result.first) {
            upper=machines;
            results=result.second;
        }
        else
            lower=machines+1;
    }

    cout << lower << endl;
    for (int i=0; i<n; i++) {
        for (int &idx:results[i]) cout << idx << " ";
        cout << 0 << endl;
    }
}

• Subtask 1: 100 / 100