Submission #499641

#TimeUsernameProblemLanguageResultExecution timeMemory
499641Shreyan_PaliwalJob Scheduling (CEOI12_jobs)C++17
45 / 100
547 ms13764 KiB
#include <algorithm> #include <iostream> #include <vector> using namespace std; vector<pair<int, int>> jobs; int n, d, m; bool works(int mid) { int counter = 0; for (int i = 0; i < m; i++) { if ((counter / mid) + 1 <= jobs[i].first + d) { counter++; } else { return false; } } return (counter / mid) + 1 <= n; } int main() { // freopen("jobscheduling.in", "r", stdin); cin >> n >> d >> m; jobs = vector<pair<int, int>>(m); for (int i = 0; i < m; i++) { cin >> jobs[i].first; jobs[i].second = i + 1; } sort(jobs.begin(), jobs.end()); int lo = 1; int hi = 1000000; while (lo != hi) { int mid = (lo + hi) / 2; if (works(mid)) { hi = mid; } else { lo = mid + 1; } } cout << lo << endl; int counter = 0; for (int i = 0; i < n; i++) { if (counter < m) for (int j = 0; j < lo; j++) { if (counter < m) // cout << 0 * (counter++) << " "; cout << jobs[counter++].second << " "; else break; } cout << 0 << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...