# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
480493 | imaginary_unit | Job Scheduling (CEOI12_jobs) | C++17 | 780 ms | 16648 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
int n, d, m, a[1'000'000];
bool ok(int mch)
{
priority_queue<int, vector<int>, greater<int> > pq;
for(int i=0; i<mch; i++){
pq.push(1);
}
for(int i=0; i<m; i++){
int cur=pq.top();
if(cur+1-a[i] > d){
return 0;
}
pq.pop();
pq.push(cur+1);
}
return 1;
}
int minMachines(int l, int r)
{
while(r-l>1){
int m=(l+r)/2;
if(ok(m)){
r=m;
}
else{
l=m;
}
}
return r;
}
int main()
{
//freopen("angry.in", "r", stdin);
//freopen("angry.out", "w", stdout);
scanf("%d %d %d", &n, &d, &m);
for(int i=0; i<m; i++){
scanf("%d", &a[i]);
}
sort(a, a+m);
int ans=minMachines(1, n);
cout << ans << '\n';
vector<int> tasks[n+1];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
for(int i=0; i<ans; i++){
pq.push({1, i});
}
for(int i=0; i<m; i++){
pair<int, int> cur=pq.top(); /// {day free, #}
pq.pop();
tasks[cur.fi].push_back(i+1);
cur.fi++;
pq.push(cur);
}
for(int i=1; i<=n; i++){
for(int j=0; j<tasks[i].size(); j++){
cout << tasks[i][j] << ' ';
}
cout << 0 << '\n';
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |