Submission #667037

#	Time	Username	Problem	Language	Result	Execution time	Memory
667037		hanlei35	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	365 ms	13900 KiB

jobs

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

int N, D, M;
pair<int,int> jobs[1000005];
bool check(int m){
    int maxD = -1;
    int j = -1;
    for(int i=0;i<N;i++){
        int count = 0;
        while(count!=m&&j!=M-1&&jobs[j+1].first<=i+1){
            maxD = max(maxD,i+1-jobs[++j].first);
            count++; 
        }
    }
    if(maxD > D) return true;
    return false;
}
int search(){
    int ans = 0;
    for(int val = M; val >= 1; val /= 2){
        while(ans+val <= M && check(ans+val)) ans += val;
    }
    return ans + 1;
}
int main(){
    cin >> N >> D >> M;
    for(int i=0;i<M;i++){
        cin >> jobs[i].first;
        jobs[i].second = i+1;
    }
    sort(jobs,jobs+M);
    int minM = search();
    cout << minM << "\n";
    int j = -1;
    for(int i=0;i<N;i++){
        int count = 0;
        while(count!=minM&&j!=M-1&&jobs[j+1].first<=i+1){
            cout << jobs[++j].second << " ";
            count++;
        }
        cout << "0\n";
    }
    return 0;
}

• Subtask 1: 100 / 100