Submission #730284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
730284	2023-04-25T15:01:32 Z	reestear	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	344 ms	13536 KB

jobs

#include <bits/stdc++.h>
using namespace std;
const int mxN = 100000;
int n, d, m;
vector <int> arr[mxN + 1];

bool check(int mid){
    queue <int> q;
    int res = 0;
    for(int i = 1; i <= n; i++){
        for(const auto &now : arr[i]){
            q.push(i);
        }
        if(!q.empty()) res = max(res, i - q.front());
        for(int j = 0; j < mid && !q.empty(); j++) q.pop();
    }

    return res <= d;
}

int main(){
    cin >> n >> d >> m;
    for(int i = 0; i < m; i++){
        int temp; cin >> temp;
        arr[temp].push_back(i + 1);
    }

    // for(int i = 1; i <= n; i++){
    //     cout << "day = " << i << " : ";
    //     for(const auto &now : arr[i]){
    //         cout << now << ' ';
    //     }
    //     cout << '\n';
    // }
    

    int low = 1, high = m;
    while(low <= high){
        int mid = (low + high) / 2;
        // cout << "mid = " << mid << '\n';
        if(check(mid)) high = mid - 1;
        else low = mid + 1;
    }

    int tot = high + 1;
    cout << tot << '\n';

    queue <int> q;
    for(int i = 1; i <= n; i++){
        for(const auto &now : arr[i]){
            q.push(now);
        }
        for(int j = 0; j < tot && !q.empty(); j++) {
            cout << q.front() << ' ';
            q.pop();
        }
        cout << "0\n";
    }

    return 0;
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:11:25: warning: unused variable 'now' [-Wunused-variable]
   11 |         for(const auto &now : arr[i]){
      |                         ^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	35 ms	4036 KB	Output is correct
2	Correct	33 ms	3984 KB	Output is correct
3	Correct	33 ms	3972 KB	Output is correct
4	Correct	35 ms	3996 KB	Output is correct
5	Correct	37 ms	4032 KB	Output is correct
6	Correct	34 ms	4000 KB	Output is correct
7	Correct	40 ms	3992 KB	Output is correct
8	Correct	35 ms	3952 KB	Output is correct
9	Correct	43 ms	4148 KB	Output is correct
10	Correct	40 ms	4044 KB	Output is correct
11	Correct	37 ms	3736 KB	Output is correct
12	Correct	77 ms	4896 KB	Output is correct
13	Correct	119 ms	6776 KB	Output is correct
14	Correct	168 ms	8280 KB	Output is correct
15	Correct	191 ms	9016 KB	Output is correct
16	Correct	264 ms	11084 KB	Output is correct
17	Correct	318 ms	12868 KB	Output is correct
18	Correct	296 ms	12676 KB	Output is correct
19	Correct	344 ms	13536 KB	Output is correct
20	Correct	315 ms	12956 KB	Output is correct