Submission #483139

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483139	2021-10-27T21:27:02 Z	jsn667	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	458 ms	30392 KB

jobs

    # include <bits/stdc++.h>
     
    using namespace std;
     
     
    struct Job{
    int index, day, deadline;
     
    };
    vector<Job> a;
    int n, d, m;
     
     
    bool cmp(Job a, Job b){
    	return a.deadline < b.deadline;
    }
     
     
     
    int main(){
    	
    	cin >> n >> d >> m;
    	a.resize(m + 1);
    	for(int i = 1; i <= m; i++){
    		Job j;
    		j.index = i;
    		cin >> j.day;
    		j.deadline = j.day + d;
    		a[i] = j;
    	}
    	sort(a.begin(), a.end(), cmp);
    	int L = 1, R = m;
    	int res = 0;
    	vector<vector<int>> resv;
    	while(L <= R){
    		int mid = L + (R - L) / 2;
    		int finished = 0;
    		bool valid = true;
            	vector<vector<int>> out(n + 1);
            	for(int i = 1, j = 1; i <= n; i++){
                    	int machines = mid;
                    	while(j <= m && i >= a[j].day && machines > 0){
                            	if(i > a[j].deadline){
    					valid = false;
    					break;
    				}
                            	out[i].push_back(a[j].index);
                            	machines--;
                            	j++;
                            	finished++;
                    	}
    			if(!valid) break;
                 
            	}
            	if(finished == m){
    			R = mid - 1;
    			res = mid;
    			resv = out;
    		}
    		else{
    			L = mid + 1;
    		}
    		
    	}
    	cout << res << "\n";
    	for(int i = 1; i <= n; i++){
    		for(int j = 0; j < (int)resv[i].size(); j++){
    			cout << resv[i][j] << " ";
    		}
    		cout << 0 << "\n";
    	}
    	
    	return 0;
    }

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	40 ms	3032 KB	Output is correct
2	Correct	37 ms	3048 KB	Output is correct
3	Correct	38 ms	3032 KB	Output is correct
4	Correct	39 ms	3032 KB	Output is correct
5	Correct	38 ms	3004 KB	Output is correct
6	Correct	46 ms	2992 KB	Output is correct
7	Correct	39 ms	3024 KB	Output is correct
8	Correct	37 ms	3024 KB	Output is correct
9	Correct	62 ms	7952 KB	Output is correct
10	Correct	68 ms	8088 KB	Output is correct
11	Correct	52 ms	3120 KB	Output is correct
12	Correct	89 ms	5964 KB	Output is correct
13	Correct	138 ms	9308 KB	Output is correct
14	Correct	221 ms	12944 KB	Output is correct
15	Correct	226 ms	14468 KB	Output is correct
16	Correct	301 ms	17708 KB	Output is correct
17	Correct	390 ms	22508 KB	Output is correct
18	Correct	391 ms	23660 KB	Output is correct
19	Correct	458 ms	30392 KB	Output is correct
20	Correct	365 ms	22612 KB	Output is correct