Submission #768301

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768301	2023-06-27T21:25:51 Z	orcslop	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	279 ms	13784 KB

jobs

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size() 

const int MAXN = 1e5; 
const int MAXM = 1e6; 

int n, d, m; 
pair<int, int> jobs[MAXM]; 
queue<int> q; 

bool check(int machines){
    while(!q.empty()) q.pop(); 
    int index = 0; 
    for(int i = 1; i <= n; i++){
        while(index < m && jobs[index].first <= i) {
            q.push(jobs[index].first); 
            index++; 
        }
        for(int j = 0; j < machines; j++){
            if(!q.empty()) {
                int sent = q.front(); 
                if(i - sent > d) return false; 
                q.pop(); 
            }
            else break; 
        }
    }
    return q.empty(); 
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> d >> m; 
    for(int i = 0; i < m; i++) {
        cin >> jobs[i].first;
        jobs[i].second = i + 1;  
    }
    sort(jobs, jobs + m); 
    int low = 1, high = INT_MAX; 
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid + 1;
    }
    // cout << check(1000000); 
    cout << low << '\n'; 

    while(!q.empty()) q.pop(); 
    int index = 0; 
    for(int i = 1; i <= n; i++){
        while(index < m && jobs[index].first <= i) {
            q.push(jobs[index].second); 
            index++; 
        }
        for(int i = 0; i < low; i++){
            if(!q.empty()) {
                int sent = q.front(); 
                cout << sent << ' '; 
                q.pop(); 
            }
            else break; 
        }
        cout << "0\n"; 
    }
    return 0; 
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	24 ms	2132 KB	Output is correct
2	Correct	24 ms	2116 KB	Output is correct
3	Correct	24 ms	2080 KB	Output is correct
4	Correct	26 ms	2048 KB	Output is correct
5	Correct	24 ms	2044 KB	Output is correct
6	Correct	25 ms	2044 KB	Output is correct
7	Correct	29 ms	2132 KB	Output is correct
8	Correct	24 ms	2048 KB	Output is correct
9	Correct	46 ms	2008 KB	Output is correct
10	Correct	40 ms	1876 KB	Output is correct
11	Correct	31 ms	1620 KB	Output is correct
12	Correct	63 ms	3156 KB	Output is correct
13	Correct	94 ms	4684 KB	Output is correct
14	Correct	135 ms	6316 KB	Output is correct
15	Correct	149 ms	7556 KB	Output is correct
16	Correct	191 ms	9036 KB	Output is correct
17	Correct	232 ms	10652 KB	Output is correct
18	Correct	255 ms	12068 KB	Output is correct
19	Correct	279 ms	13784 KB	Output is correct
20	Correct	232 ms	10648 KB	Output is correct