Submission #768278

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768278	2023-06-27T21:05:01 Z	orcslop	Job Scheduling (CEOI12_jobs)	C++17	15 / 100	211 ms	17060 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++){
        int cnt = 0; 
        while(index < m && jobs[index].first == i) {
            q.push(i); 
            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 = 0, 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; 
}

Compilation message

jobs.cpp: In function 'bool check(int)':
jobs.cpp:16:13: warning: unused variable 'cnt' [-Wunused-variable]
   16 |         int cnt = 0;
      |             ^~~

Subtask #1

15.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	15 ms	2380 KB	Output isn't correct
2	Incorrect	15 ms	2412 KB	Output isn't correct
3	Incorrect	15 ms	2392 KB	Output isn't correct
4	Incorrect	15 ms	2348 KB	Output isn't correct
5	Incorrect	16 ms	2388 KB	Output isn't correct
6	Incorrect	17 ms	2348 KB	Output isn't correct
7	Incorrect	15 ms	2376 KB	Output isn't correct
8	Incorrect	15 ms	2352 KB	Output isn't correct
9	Incorrect	21 ms	2120 KB	Output isn't correct
10	Incorrect	21 ms	2132 KB	Output isn't correct
11	Incorrect	19 ms	1992 KB	Output isn't correct
12	Incorrect	40 ms	3880 KB	Output isn't correct
13	Incorrect	59 ms	5688 KB	Output isn't correct
14	Correct	115 ms	8524 KB	Output is correct
15	Incorrect	100 ms	9424 KB	Output isn't correct
16	Incorrect	133 ms	11804 KB	Output isn't correct
17	Correct	204 ms	14868 KB	Output is correct
18	Incorrect	161 ms	14972 KB	Output isn't correct
19	Incorrect	187 ms	17060 KB	Output isn't correct
20	Correct	211 ms	14676 KB	Output is correct