Submission #768294

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768294	2023-06-27T21:15:48 Z	orcslop	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	197 ms	13724 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 i = 0; i < machines; i++){
            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 = m; 
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (check(mid)) high = mid;
        else low = mid + 1;
    }
    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

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	2132 KB	Output isn't correct
2	Incorrect	16 ms	2044 KB	Output isn't correct
3	Incorrect	15 ms	2132 KB	Output isn't correct
4	Incorrect	16 ms	2104 KB	Output isn't correct
5	Incorrect	16 ms	2144 KB	Output isn't correct
6	Incorrect	15 ms	2072 KB	Output isn't correct
7	Incorrect	16 ms	2048 KB	Output isn't correct
8	Incorrect	16 ms	2088 KB	Output isn't correct
9	Incorrect	21 ms	1904 KB	Output isn't correct
10	Incorrect	21 ms	1868 KB	Output isn't correct
11	Incorrect	19 ms	1704 KB	Output isn't correct
12	Incorrect	44 ms	3148 KB	Output isn't correct
13	Incorrect	58 ms	4592 KB	Output isn't correct
14	Correct	109 ms	6632 KB	Output is correct
15	Incorrect	99 ms	7556 KB	Output isn't correct
16	Incorrect	121 ms	9060 KB	Output isn't correct
17	Correct	196 ms	11400 KB	Output is correct
18	Incorrect	158 ms	12076 KB	Output isn't correct
19	Incorrect	182 ms	13724 KB	Output isn't correct
20	Correct	197 ms	11500 KB	Output is correct