Submission #483134

#	Time	Username	Problem	Language	Result	Execution time	Memory
483134		jsn667	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	496 ms	39708 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;
                	out[i].push_back(0);
        	}
        	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 < resv[i].size(); j++){
			cout << resv[i][j] << " ";
		}
		cout << "\n";
	}
	
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:67:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for(int j = 0; j < resv[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100