Submission #426304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426304	2021-06-13T17:15:14 Z	apotosaurus	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	629 ms	13780 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	1584 KB	Output is correct
2	Correct	53 ms	1600 KB	Output is correct
3	Correct	54 ms	1596 KB	Output is correct
4	Correct	54 ms	1604 KB	Output is correct
5	Correct	57 ms	1624 KB	Output is correct
6	Correct	56 ms	1592 KB	Output is correct
7	Correct	55 ms	1588 KB	Output is correct
8	Correct	53 ms	1592 KB	Output is correct
9	Correct	196 ms	1820 KB	Output is correct
10	Correct	200 ms	1856 KB	Output is correct
11	Correct	52 ms	1580 KB	Output is correct
12	Correct	114 ms	3120 KB	Output is correct
13	Correct	153 ms	4560 KB	Output is correct
14	Correct	240 ms	6168 KB	Output is correct
15	Correct	269 ms	7524 KB	Output is correct
16	Correct	342 ms	9084 KB	Output is correct
17	Correct	395 ms	10564 KB	Output is correct
18	Correct	426 ms	12048 KB	Output is correct
19	Correct	629 ms	13780 KB	Output is correct
20	Correct	394 ms	10512 KB	Output is correct