Submission #426267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426267	2021-06-13T16:20:23 Z	apotosaurus	Job Scheduling (CEOI12_jobs)	C++11	85 / 100	610 ms	17048 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

85.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	1884 KB	Output is correct
2	Correct	60 ms	1892 KB	Output is correct
3	Correct	55 ms	1888 KB	Output is correct
4	Correct	57 ms	1912 KB	Output is correct
5	Correct	54 ms	1960 KB	Output is correct
6	Correct	58 ms	2036 KB	Output is correct
7	Correct	71 ms	1964 KB	Output is correct
8	Correct	61 ms	1860 KB	Output is correct
9	Correct	202 ms	2100 KB	Output is correct
10	Correct	202 ms	2204 KB	Output is correct
11	Correct	52 ms	1956 KB	Output is correct
12	Incorrect	101 ms	3908 KB	Output isn't correct
13	Correct	171 ms	5688 KB	Output is correct
14	Incorrect	233 ms	8004 KB	Output isn't correct
15	Incorrect	287 ms	9428 KB	Output isn't correct
16	Correct	338 ms	11972 KB	Output is correct
17	Correct	397 ms	13836 KB	Output is correct
18	Correct	424 ms	15104 KB	Output is correct
19	Correct	610 ms	17048 KB	Output is correct
20	Correct	404 ms	13940 KB	Output is correct