Submission #465385

#	Time	Username	Problem	Language	Result	Execution time	Memory
465385		Uhm	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	625 ms	13812 KiB

jobs

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, d;
vector<pair<int, int> > arr;


bool canWork(int val){
    int numLeft=val-1;
    int day=arr[0].first;
    for(int i=2;i<m;i++){
        bool setNum=false;
        if(numLeft==0){
            setNum=true;
            day++;
        }
        if(day<arr[i].first){
            setNum=true;
            day=arr[i].first;
        }
        if(day-arr[i].first>d)
            return false;
        if(setNum)
            numLeft=val;
        numLeft--;
    }
    return true;
}

void makeSol(int val){
    int numLeft=val-1;
    int day=arr[0].first;
    for(int i=2;i<m;i++){
        bool setNum=false;
        if(numLeft==0){
            setNum=true;
            day++;
        }
        if(day<arr[i].first){
            setNum=true;
            day=arr[i].first;
        }
        arr[i].first=day;
        if(setNum)
            numLeft=val;
        numLeft--;
    }
}

int main(){
    cin>>n>>d>>m;
    for(int i=0;i<m;i++){
        int t;
        cin>>t;
        arr.push_back(make_pair(t, i+1));
    }
    sort(arr.begin(), arr.end());
    int left=1;
    int right=m;
    while(left<right){
        int mid=left+right;
        mid/=2;
        if(canWork(mid))
            right=mid;
        else
            left=mid+1;
    }
    cout<<left<<endl;
    makeSol(left);
    int day=1;
    bool fir=true;
    for(int i=0;i<m;i++){
        if(day<arr[i].first){
            cout<<" 0"<<endl;
            day++;
            fir=true;
            while(day<arr[i].first){
                cout<<0<<endl;
                day++;
            }
        }
        if(!fir)
            cout<<" ";
        cout<<arr[i].second;
        fir=false;
    }
    while(day<=n){
        if(!fir){
            fir=true;
            cout<<" ";
        }
        cout<<0<<endl;
        day++;
    }
}

• Subtask 1: 100 / 100