Submission #466892

#	Time	Username	Problem	Language	Result	Execution time	Memory
466892		gordonsun	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	597 ms	15456 KiB

jobs

#include<bits/stdc++.h>
using namespace std;
pair<int, int> p[1000005];

int N, D, M;
bool check(int machines){
    int m[machines];
    memset(m,0,sizeof(m));
    int index = 0;
    for (int i = 0; i < N; i++){
        if (index == machines){
            index = 0;
        }
        m[index] = max(m[index]+1,p[i].first+1);
        if (m[index] > p[i].first+D){
            return false;
        }
        index++;
    }
    return true;
}
int main(){
    cin >> N >> D >> M;
    for (int i = 0; i < M; i++){
        cin >> p[i].first;
        p[i].second = i+1;
    }
    sort(p,p+M);
    int l = 0;
    int r = M;
    while (l != r){
        int mid = (l+r)/2;
        if (check(mid)){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }
    cout << l << endl;
    int ntracker = 0;
    int index = 0;
    while(true){
        if (ntracker == N){
            break;
        }
        for (int j = 0; j < l; j++){
            if (index == M){
                break;
            }
            cout << p[index].second << " ";
            index++;
        }
        cout << 0 << endl;
        ntracker++;
    }
}

• Subtask 1: 0 / 100