Submission #469654

#	Time	Username	Problem	Language	Result	Execution time	Memory
469654		goatgm03	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1100 ms	7244 KiB

jobs

#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
int main(){
    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=n,sol=n;
    while(lo<hi){
        int mid=(hi-lo)/2,cnt=0;
        int day=1,cur=0;
        for(int i=0;i<m;i++){
            if(t[i].f<=day&&day<=t[i].f+d){
                cnt++;
                cur++;
            }
            if(cur==mid){
                cur=0;
                day++;
            }
        }
        if(cnt<n){
            lo=mid+1;
        }
        else{
            hi=mid;
            sol=min(sol,mid);
        }
    }
    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==sol){
            cur=0;
            day++;
        }
    }
    cout<<sol<<endl;
    for(int i=1;i<=n;i++){
        if(!each_day[i].size()){
            cout<<"0\n";
            continue;
        }
        for(int j:each_day[i]){
            cout<<j<<' ';
        }
        cout<<"0\n";
    }
}

• Subtask 1: 0 / 100