Submission #426301

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
426301	2021-06-13T17:14:18 Z	apotosaurus	Job Scheduling (CEOI12_jobs)	C++11	90 / 100	627 ms	17140 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

90.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	1860 KB	Output is correct
2	Correct	58 ms	1888 KB	Output is correct
3	Correct	54 ms	1884 KB	Output is correct
4	Correct	66 ms	1868 KB	Output is correct
5	Correct	56 ms	2000 KB	Output is correct
6	Correct	54 ms	1960 KB	Output is correct
7	Correct	60 ms	1884 KB	Output is correct
8	Correct	57 ms	2008 KB	Output is correct
9	Correct	218 ms	2088 KB	Output is correct
10	Correct	215 ms	2044 KB	Output is correct
11	Correct	64 ms	1988 KB	Output is correct
12	Incorrect	100 ms	3876 KB	Output isn't correct
13	Correct	153 ms	5772 KB	Output is correct
14	Incorrect	236 ms	8020 KB	Output isn't correct
15	Correct	253 ms	9412 KB	Output is correct
16	Correct	343 ms	11872 KB	Output is correct
17	Correct	394 ms	13860 KB	Output is correct
18	Correct	442 ms	15172 KB	Output is correct
19	Correct	627 ms	17140 KB	Output is correct
20	Correct	484 ms	13840 KB	Output is correct