oj.uz

Submission #680287

# Submission time Handle Problem Language Result Execution time Memory
680287 2023-01-10T13:17:02 Z SriniV Job Scheduling (CEOI12_jobs) C++14
100 / 100
 368 ms 17140 KB 
#include <bits/stdc++.h>

using namespace std;

int n , d , m;
vector<pair < int , int > > jobs;
bool valid(int machines){
	
	int day = 1;
	int count = 0;
	for(auto job : jobs){
		if(job.first>day){
			count = 0;
			day = job.first;	
		}
		if(count==machines){
			count = 0;
			day++;
		}
		if(day - job.first > d){
			return false;
		}
		count++;
	}
	return true;

}
int main(){
	cin >> n >> d >> m;
	jobs.resize(m);
	for(int i = 0;i<m;i++){
		cin >> jobs[i].first;
		jobs[i].second = i+1;
	}
	sort(jobs.begin() , jobs.end());
	int left = 1 , right = m;
	int answer = -1;
	while(left<=right){

		int middle = left + (right - left)/2;
		if(valid(middle)){
			answer = middle;
			right = middle - 1;
		} else {
			left = middle + 1;
		}
	}
	cout << answer<<"\n";
	int count = 0;
	for(int day = 1;day<=n;day++){
		for(int i = 0;i<answer;i++){
			if(jobs[count].first>day||count==m)break;
			cout << jobs[count++].second<<" ";
		}
		cout << 0 << "\n";
	}

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 1868 KB Output is correct
2 Correct 30 ms 1892 KB Output is correct
3 Correct 29 ms 1892 KB Output is correct
4 Correct 29 ms 1932 KB Output is correct
5 Correct 32 ms 1868 KB Output is correct
6 Correct 29 ms 1968 KB Output is correct
7 Correct 34 ms 1864 KB Output is correct
8 Correct 29 ms 1896 KB Output is correct
9 Correct 46 ms 2104 KB Output is correct
10 Correct 45 ms 2088 KB Output is correct
11 Correct 39 ms 1972 KB Output is correct
12 Correct 77 ms 3892 KB Output is correct
13 Correct 117 ms 5768 KB Output is correct
14 Correct 173 ms 8028 KB Output is correct
15 Correct 195 ms 9452 KB Output is correct
16 Correct 248 ms 11864 KB Output is correct
17 Correct 298 ms 13844 KB Output is correct
18 Correct 341 ms 15056 KB Output is correct
19 Correct 368 ms 17140 KB Output is correct
20 Correct 297 ms 13900 KB Output is correct