제출 #499650

#제출 시각아이디문제언어결과실행 시간메모리
499650Shreyan_PaliwalJob Scheduling (CEOI12_jobs)C++17
100 / 100
567 ms13636 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; // int day = 1; // for (int i = 0; i < m; i++) { // if (day <= jobs[i].first + d) { // if (day < jobs[i].first) { // counter = 1 % mid; // day = jobs[i].first + (counter == 0 ? 1 : 0); // } else { // counter = (counter + 1) % mid; // if (counter == 0) day++; // } // } else { // return false; // } // } // return (counter == 0 ? day - 1 : day) <= n; int counter = mid; for (int i = 0; i < m; i++) { if ((counter / mid) <= jobs[i].first + d) { if ((counter / mid) < jobs[i].first) { counter = jobs[i].first * mid + 1; } else { counter++; } } else { return false; } } counter--; return (counter / mid) <= 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 = 1; i < n + 1; i++) { if (counter == m) { cout << 0 << endl; continue; } if (jobs[counter].first <= i) { for (int j = 0; j < lo; j++) { if (counter == m) break; cout << jobs[counter++].second << " "; } } cout << 0 << 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...