Submission #426304

#	Time	Username	Problem	Language	Result	Execution time	Memory
426304		apotosaurus	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	629 ms	13780 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

#define DEBUG false
#define cdbg if (!DEBUG) {} else cerr

#define INFILE "jobs.in"
#define OUTFILE "jobs.out"

int N,D,M;
vector<pair<int,int>> inpt;

void readInput(){
    cin >> N >> D >> M;
    inpt.resize(M);
    for (int i = 0; i < M; i++){
        cin >> inpt[i].first;
        inpt[i].second = i+1;
    }
    sort(inpt.begin(), inpt.end());
}

bool works(int m){
    int curDay = 1;
    int curPerDay = 0;
    for (int i = 0; i < M; i++){
        if (inpt[i].first > curDay){
            curDay = inpt[i].first;
            curPerDay = 1;
        }
        else if (inpt[i].first < curDay - D){
            return false;
        }
        else if (inpt[i].first >= curDay - D){
            curPerDay++;
        }
        if (curPerDay >= m){
            curPerDay = 0;
            curDay++;
        }
        // if (curDay > N){
        //     return false;
        // }
    }
    return true;
}

void printVec(int m){
    int curDay = 1;
    int curPerDay = 0;
    for (int i = 0; i < M; i++){
        if (inpt[i].first > curDay){
            for (int j = curDay; j < inpt[i].first; j++){
                cout << 0 << endl;
            }
            curDay = inpt[i].first;
            curPerDay = 1;
        }
        else if (inpt[i].first >= curDay - D){
            cout << inpt[i].second << " ";
            curPerDay++;
        }
        if (curPerDay >= m){
            cout << 0 << endl;
            curPerDay = 0;
            curDay++;
        }
    }
    for (int i = curDay; i <= N; i++){
        cout << 0 << endl;
    }
}

void solve(){
    int lB = 1;
    int uB = M;
    while (lB < uB){
        int mid = (lB + uB) / 2;
        if (works(mid)){
            uB = mid;
        }
        else{
            lB = mid+1;
        }
    }
    cout << uB << endl;
    printVec(uB);
}

int main(){
    
    // freopen(INFILE, "r", stdin); // redirects standard input
    // freopen(OUTFILE, "w", stdout); // redirects standard output
    
    readInput();
    solve();

    return 0;
}

• Subtask 1: 100 / 100