Submission #1172914

#TimeUsernameProblemLanguageResultExecution timeMemory
1172914Roman70Job Scheduling (CEOI12_jobs)C++20
85 / 100
453 ms80624 KiB
#include <bits/stdc++.h> using namespace std; int n, d, m; vector<int> submitDays[100000]; bool ok(int c) { priority_queue<int, vector<int>, greater<int>> pq; for (int day = 0; day < n; ++day) { // Add all jobs submitted on this day to the priority queue for (int job : submitDays[day]) { int deadline = day + d; pq.push(deadline); } // Process up to c jobs on this day int processed = 0; while (!pq.empty() && processed < c) { int deadline = pq.top(); if (deadline < day) { return false; // Can't process this job anymore } pq.pop(); processed++; } } return pq.empty(); } void printSchedule(int c) { vector<queue<int>> dayJobs(n); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for (int day = 0; day < n; ++day) { // Add jobs submitted on this day to the priority queue (deadline, job index) for (int job : submitDays[day]) { int deadline = day + d; pq.push({deadline, job}); } // Collect up to c jobs for this day int processed = 0; vector<int> jobs; while (!pq.empty() && processed < c) { auto [deadline, job] = pq.top(); if (deadline < day) { // This should not happen as we checked in ok() pq.pop(); continue; } pq.pop(); jobs.push_back(job); processed++; } // Output the jobs for this day for (int job : jobs) { cout << job << " "; } cout << "0\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> d >> m; for (int i = 0; i < m; ++i) { int s; cin >> s; submitDays[s - 1].push_back(i + 1); // Convert to 0-based day } int left = 1, right = m; int answer = m; while (left <= right) { int mid = (left + right) / 2; if (ok(mid)) { answer = mid; right = mid - 1; } else { left = mid + 1; } } cout << answer << "\n"; printSchedule(answer); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...