Submission #667028

#	Time	Username	Problem	Language	Result	Execution time	Memory
667028		hanlei35	Job Scheduling (CEOI12_jobs)	C++17	35 / 100	1085 ms	20488 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 = 0;
    multiset<int> delayed;
    for(int i=0;i<N;i++){
        while(j!=M&&jobs[j].first==i+1){
            delayed.insert(i+1);
            j++;
        }
        int count = 0;
        while(count!=m&&!delayed.empty()){
            maxD = max(maxD,i+1-*delayed.begin());
            delayed.erase(delayed.begin());
            count++;
        }
    }
    if(maxD > D) return true;
    return false;
}
int search(){
    int ans = 0;
    for(int val = N; val >= 1; val /= 2){
        while(ans+val <= N && 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 = 0; multiset<pair<int,int>> delayed;
    for(int i=0;i<N;i++){
        while(j!=M&&jobs[j].first==i+1){
            delayed.insert({jobs[j].first,jobs[j].second});
            j++;
        }
        int count = 0;
        while(count!=minM&&!delayed.empty()){
            cout << (*delayed.begin()).second << " ";
            delayed.erase(delayed.begin());
            count++;
        }
        cout << "0\n";
    }
    return 0;
}

• Subtask 1: 35 / 100