# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
854395 | 2023-09-27T09:38:26 Z | anhphant | Job Scheduling (CEOI12_jobs) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl '\n' ll N, D, M; pair<ll, ll> A[100007]; void initialize() { ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> D >> M; for(int i = 1; i <= M; ++i) { cin >> A[i].first; A[i].second = i; } sort(A + 1, A + 1 + M); } bool check(ll MachinesCnt) { int idx = 1; for(int day = 1; day <= N; ++day) { ll used_machines_in_day = 0; while(idx <= M && used_machines_in_day < MachinesCnt) { if (A[idx].first + D < day) return 0; if (day < A[idx].first) break; used_machines_in_day++; idx++; } } return idx > M; } void construct(ll MachinesCnt) { int idx = 1; for(int day = 1; day <= N; ++day) { ll used_machines_in_day = 0; while(idx <= M && used_machines_in_day < MachinesCnt) { if (A[idx].first + D < day) return 0; if (day < A[idx].first) break; cout << A[idx].second << " "; used_machines_in_day++; idx++; } cout << 0 << endl; } } void process() { ll l = 1, r = M; while(l < r) { ll mid = (l + r) / 2; if (check(mid)) r = mid; else l = mid + 1; } cout << l << endl; construct(l); } int main() { initialize(); process(); }