#include <bits/stdc++.h>
using namespace std;
bool ifPossible(vector<int>& jobs, int x, int d) {
deque<pair<int,int>> dq;
for(int i = 0; i < jobs.size(); i++) {
if(!dq.empty() && dq.front().first + d < i) return 0;
int machines = x;
while(!dq.empty() && machines) {
if(dq.front().second > machines) {
dq.front().second -= machines;
machines = 0;
}
else {
machines -= dq.front().second;
dq.pop_front();
}
}
if(jobs[i] > machines) dq.push_back({i, jobs[i] - machines});
}
return 1;
}
int main() {
int n, m, d;
cin >> n >> d >> m;
vector<int> jobs(n);
vector<deque<int>> ids(n);
for(int i = 0; i < m; i++) {
int x;
cin >> x;
x--;
jobs[x]++;
ids[x].push_back(i + 1);
}
// When we are at the ith day, jobs with deadline upto i - 1 must be completed
// for(int i = 0; i < 7; i++) {
// cout << jobs[i] << " ";
// }
// cout << endl;
// for(int i = 0; i < n; i++) {
// for(int x : ids[i]) cout << x << " ";
// cout << endl;
// }
int L = 0,R = m;
while(R - L > 1) {
int mid = (L + R) / 2;
if(ifPossible(jobs, mid, d)) R = mid;
else L = mid;
}
cout << R << endl;
deque<pair<int,int>> dq;
vector<vector<int>> output(n);
for(int i = 0; i < jobs.size(); i++) {
int machines = R;
while(!dq.empty() && machines) {
if(dq.front().second > machines) {
dq.front().second -= machines;
auto& ls = ids[dq.front().first];
while(machines) {
output[i].push_back(ls.front());
ls.pop_front();
machines--;
}
}
else {
auto& ls = ids[dq.front().first];
while(dq.front().second) {
output[i].push_back(ls.front());
ls.pop_front();
machines--;
dq.front().second--;
}
dq.pop_front();
}
}
if(jobs[i] > machines) {
dq.push_back({i, jobs[i] - machines});
auto& ls = ids[i];
while(machines) {
output[i].push_back(ls.front());
ls.pop_front();
machines--;
}
}
else {
auto& ls = ids[i];
while(!ls.empty()) {
output[i].push_back(ls.front());
ls.pop_front();
machines--;
}
}
}
for(int i = 0; i < n; i++) {
for(int x : output[i]) cout << x << " ";
cout << 0 << endl;
}
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
