Submission #465385

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
465385	2021-08-15T19:32:33 Z	Uhm	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	625 ms	13812 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	52 ms	1720 KB	Output is correct
2	Correct	53 ms	1772 KB	Output is correct
3	Correct	53 ms	1764 KB	Output is correct
4	Correct	52 ms	1748 KB	Output is correct
5	Correct	55 ms	1712 KB	Output is correct
6	Correct	52 ms	1740 KB	Output is correct
7	Correct	52 ms	1788 KB	Output is correct
8	Correct	52 ms	1728 KB	Output is correct
9	Correct	197 ms	1908 KB	Output is correct
10	Correct	196 ms	1916 KB	Output is correct
11	Correct	50 ms	1704 KB	Output is correct
12	Correct	102 ms	3248 KB	Output is correct
13	Correct	152 ms	4676 KB	Output is correct
14	Correct	232 ms	6232 KB	Output is correct
15	Correct	249 ms	7636 KB	Output is correct
16	Correct	344 ms	9284 KB	Output is correct
17	Correct	389 ms	10632 KB	Output is correct
18	Correct	420 ms	12152 KB	Output is correct
19	Correct	625 ms	13812 KB	Output is correct
20	Correct	395 ms	10764 KB	Output is correct