# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
469827 | goatgm03 | Job Scheduling (CEOI12_jobs) | C++17 | 206 ms | 11604 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;
#define ll long long
#define pb push_back
#define v vector
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define f first
#define s second
const int mx=1e6+5;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
// clock_t startTime = clock();
int n,d,m;
cin>>n>>d>>m;
v<pii>t(m);
for(int i=0;i<m;i++){
cin>>t[i].f;
t[i].s=i+1;
}
sort(all(t));
int lo=1,hi=m,sol=m;
while(lo<hi){
int mid=(hi+lo)/2,cnt=0;
int day=1,cur=0;
bool too_many_machines=false;
for(int i=0;i<m;i++){
if(cur==mid){
day++;
cur=0;
}
if(t[i].f<=day&&day<=t[i].f+d){
cnt++;
cur++;
}
else if(t[i].f>day){
too_many_machines=true;
break;
}
// if(day>n||cnt==m)
// break;
}
if(too_many_machines){
hi=mid-1;
// sol=min(sol,mid);
}
else{
lo=mid+1;
}
// cout<<mid<<endl;
}
int day=1,cur=0;
v<v<int> >each_day(n+1);
for(int i=0;i<m;i++){
if(t[i].f<=day&&day<=t[i].f+d){
cur++;
each_day[day].pb(t[i].s);
}
if(cur==lo){
day++;
cur=0;
}
}
cout<<lo<<endl;
for(int i=1;i<=n;i++){
if((int)each_day[i].size()==0){
cout<<"0\n";
continue;
}
for(int j:each_day[i])
cout<<j<<' ';
cout<<"0\n";
}
// cout << double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |