#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 time | Memory | Grader output |
---|
Fetching results... |