Submission #97645

#	Time	Username	Problem	Language	Result	Execution time	Memory
97645		dalgerok	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	286 ms	13752 KiB

jobs

#include<bits/stdc++.h>
using namespace std;


const int N = 1e6 + 5;




int n, d, m;
pair < int, int > a[N];

inline bool check(int x){
    int i = 1, day = 0;
    while(i <= m){
        day += 1;
        int j = i;
        while(j <= min(m, i + x - 1) && day >= a[j].first){
            if(a[j].first + d < day){
                return false;
            }
            j += 1;
        }
        i = j;
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> d >> m;
    for(int i = 1; i <= m; i++){
        cin >> a[i].first;
        a[i].second = i;
    }
    sort(a + 1, a + m + 1);
    int l = 1, r = m;
    while(l < r){
        int mid = (r + l) >> 1;
        if(check(mid)){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }
    cout << l << "\n";
    int i = 1, day = 0;
    for(int it = 1; it <= n; it++){
        day += 1;
        int j = i;
        while(j <= min(m, i + l - 1) && day >= a[j].first){
            cout << a[j].second << " ";
            j += 1;
        }
        cout << "0\n";
        i = j;
    }
}

• Subtask 1: 100 / 100