# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
533091 | Bench0310 | Job Scheduling (CEOI12_jobs) | C++17 | 274 ms | 22748 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>
using namespace std;
typedef long long ll;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,d,m;
cin >> n >> d >> m;
vector<int> v[n+1];
for(int i=1;i<=m;i++)
{
int x;
cin >> x;
v[x].push_back(i);
}
vector<vector<int>> res(n+1);
auto go=[&](int lim)->bool
{
vector<int> cnt(n+1,0);
int idx=n;
res.assign(n+1,{});
for(int i=n;i>=1;i--)
{
for(int id:v[i])
{
while(idx>i+d||cnt[idx]==lim) idx--;
if(idx==i-1) return 0;
res[idx].push_back(id);
cnt[idx]++;
}
}
return 1;
};
int l=0,r=m;
while(l<r-1)
{
int lim=(l+r)/2;
if(go(lim)) r=lim;
else l=lim;
}
cout << r << "\n";
go(r);
for(int i=1;i<=n;i++)
{
for(int id:res[i]) cout << id << " ";
cout << "0\n";
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |