제출 #483139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483139		jsn667	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	458 ms	30392 KiB

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 / 100