Submission #1104712

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1104712	2024-10-24T09:12:45 Z	Muhammet	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	261 ms	13876 KB

jobs

#include <bits/stdc++.h>

using namespace std;

#define ff first
#define ss second

int T, n, m, d;

vector <pair<int,int>> a;

bool check(int x){
	int ind = -1, day = 0;
	while(ind < m-1){
		day++;
		for(int i = ind+1; i <= min(ind+x,m-1); i++){
			if(day < a[i].ff){
				ind = i-1;
				ind -= x;
				break;
			}
			if(a[i].ff + d < day){
				return false;
			}
		}
		ind += x;
	}
	if(day > n) return false;
	return true;
}

int main(){
	cin >> n >> d >> m;
	a.resize(m);
	for(int i = 0; i < m; i++){
		cin >> a[i].ff;
		a[i].ss = i+1;
	}
	sort(a.begin(), a.end());
	int l = 1, r = m, k = m;
	while(l <= r){
		int md = (l + r) / 2;
		if(check(md)){
			r = md-1;
			k = md;
		}
		else {
			l = md+1;
		}
	}
	cout << k << '\n';
	int ind = -1, cnt = 0;
	while(ind < m-1){
		cnt++;
		for(int i = ind+1; i <= min(ind+k,m-1); i++){
			if(cnt < a[i].ff){
				ind = i-1;
				ind -= k;
				break;
			}
			cout << a[i].ss << " ";
		}
		ind += k;
		cout << "0\n";
	}
	for(int i = cnt+1; i <= n; i++){
		cout << "0\n";
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1616 KB	Output is correct
2	Correct	20 ms	1748 KB	Output is correct
3	Correct	20 ms	1616 KB	Output is correct
4	Correct	20 ms	1616 KB	Output is correct
5	Correct	20 ms	1608 KB	Output is correct
6	Correct	20 ms	1616 KB	Output is correct
7	Correct	20 ms	1752 KB	Output is correct
8	Correct	20 ms	1616 KB	Output is correct
9	Correct	27 ms	1948 KB	Output is correct
10	Correct	27 ms	1872 KB	Output is correct
11	Correct	27 ms	1616 KB	Output is correct
12	Correct	54 ms	3148 KB	Output is correct
13	Correct	81 ms	4568 KB	Output is correct
14	Correct	116 ms	6124 KB	Output is correct
15	Correct	157 ms	7668 KB	Output is correct
16	Correct	195 ms	9216 KB	Output is correct
17	Correct	205 ms	10576 KB	Output is correct
18	Correct	238 ms	12104 KB	Output is correct
19	Correct	261 ms	13876 KB	Output is correct
20	Correct	234 ms	10568 KB	Output is correct