Submission #698908

#	Time	Username	Problem	Language	Result	Execution time	Memory
698908		Smeagol	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	380 ms	17180 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,d,m;
    cin>>n>>d>>m;
    vector<pair<int,int>> req(m);
    for(int i=0;i<m;i++){
        cin>>req[i].first;
        req[i].second=i+1;
    }
    sort(req.begin(),req.end());

    int lo=0,hi=1e9,ans=1e9;
    while(lo<=hi){
        int mid=lo+(hi-lo)/2;

        bool can=true;
        int p=0;
        for(int i=1;i<=n;i++){
            if(!can)break;
            for(int t=0;t<mid&&p<m;t++){
                if(req[p].first>i) break;
                if(i-req[p].first>d){
                    can=false;
                    break;
                }
                p++;
            }
        }
        if(p<m) can=false;

        if(can){
            hi=mid-1;
            ans=min(ans,mid);
        }
        else lo=mid+1;
    }
    cout<<ans<<"\n";

    int p=0;
    for(int i=1;i<=n;i++){
        for(int t=0;t<ans&&p<m;t++){
            if(req[p].first>i)break;
            cout<<req[p].second<<" ";
            p++;
        }
        cout<<"0\n";
    }
}

• Subtask 1: 100 / 100