Submission #775459

#	Time	Username	Problem	Language	Result	Execution time	Memory
775459		kirakaminski968	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	394 ms	17940 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
vector<pair<int,int>> jobs(MAXN);
int N,M,D;
bool check(int x){
    for(int i = 1;i<=M;++i){
        if(i/x > jobs[i].first+D) return false;
    }
    if(M/x > N) return false;
    return true;
}
int main()
{
    cin >> N >> D >> M;
    jobs.resize(M+1);
    for(int i = 1;i<=M;++i){cin >> jobs[i].first; jobs[i].second = i;}
    sort(jobs.begin(),jobs.end());
    //for(auto p : jobs) cout << p.first << " ";
    //cout << "\n";
    int lo = 1, hi = MAXN;
    while(lo < hi){
        int mid = (lo+hi)/2;
        if(check(mid)){
            hi = mid;
        }
        else{
            lo = mid+1;
        }
    }
    cout << lo << "\n";
    int cur = 1;
    for(int i = 1;i<=M;++i){
        if(i/lo == cur+1){
            cout << "0 \n" << jobs[i].second << " ";
            cur++;
        }
        else cout << jobs[i].second << " ";
    }
    cout << "\n";
    while(cur < N){
        cout << "0\n";
        cur++;
    }
    return 0;
}

• Subtask 1: 0 / 100