Submission #556132

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
556132	2022-05-02T12:48:52 Z	dhruv_kalmekh	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	579 ms	29704 KB

jobs

#include <bits/stdc++.h>
using namespace std;

int n,m,d;
vector<pair<int,int>> vec;


pair<bool,vector<vector<int>>> f(int x){
	vector<vector<int>> schedule(n);
	int req=0;
	for(int day=1;day<=n;day++){
		for(int i=0;i<x;i++){
			if(vec[req].first>day){
				break;
			}
			if(vec[req].first+d >= day){
				schedule[day-1].push_back(vec[req++].second);
			}
			else{
				return make_pair(false,schedule);
			}
			if(req==m){
				return make_pair(true,schedule);
			}
		}
	}
	return make_pair(false,schedule);
}

int main(){
	cin >> n >> d >> m;
	vec.resize(m);
	for(int i=0;i<m;i++){
		int day;
		cin >> day;
		vec[i] = make_pair(day,i+1);
	}
	sort(vec.begin(),vec.end());
	vector<vector<int>> result;
	int l=0,r=m;
	while(l<r){
		int mid = l + (r-l)/2;
		pair<bool,vector<vector<int>>> cur = f(mid);
		if(cur.first){
			r = mid; 
			result = cur.second;
		}
		else{
			l = mid+1;
		}
	}
	cout << l << "\n";
	for(int i=0;i<n;i++){
		for(int j : result[i]){
			cout << j << " ";
		}
		cout << 0 << "\n";
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	3216 KB	Output is correct
2	Correct	43 ms	3264 KB	Output is correct
3	Correct	42 ms	3240 KB	Output is correct
4	Correct	41 ms	3232 KB	Output is correct
5	Correct	41 ms	3224 KB	Output is correct
6	Correct	41 ms	3332 KB	Output is correct
7	Correct	42 ms	3256 KB	Output is correct
8	Correct	45 ms	3336 KB	Output is correct
9	Correct	114 ms	9936 KB	Output is correct
10	Correct	93 ms	9980 KB	Output is correct
11	Correct	53 ms	3096 KB	Output is correct
12	Correct	107 ms	5740 KB	Output is correct
13	Correct	148 ms	9664 KB	Output is correct
14	Correct	257 ms	12732 KB	Output is correct
15	Correct	317 ms	12772 KB	Output is correct
16	Correct	399 ms	18664 KB	Output is correct
17	Correct	495 ms	22128 KB	Output is correct
18	Correct	494 ms	21568 KB	Output is correct
19	Correct	579 ms	29704 KB	Output is correct
20	Correct	452 ms	22196 KB	Output is correct