Submission #1181390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181390		peteza	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	268 ms	23184 KiB

jobs

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

int n, d, m, x;
vector<pair<int, int>> vec;

bool solvable(int mcnt, bool printmode) {
    vector<vector<int>> ans;
    ans.push_back({});
    for(int i=0;i<m;i++) {
        while(ans.size() < vec[i].first) ans.push_back({});
        if(ans.back().size() >= mcnt) ans.push_back({});
        if(ans.size() - vec[i].first > d) return 0;
        ans.back().push_back(vec[i].second);
    }
    while(ans.size() < n) ans.push_back({});
    if(printmode) {
        for(auto &e:ans) {
            for(auto &E:e) cout << E << ' ';
            cout << "0\n";
        }
    }
    return 1;
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> d >> m;
    for(int i=1;i<=m;i++) {
        cin >> x;
        vec.emplace_back(x, i);
    }
    sort(vec.begin(), vec.end());
    int l = 1, r = m, mid = -1;
    while(l <= r) {
        mid = (l+r) >> 1;
        if(solvable(mid, 0)) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << '\n';
    auto e = solvable(l, 1);
}

• Subtask 1: 100 / 100