Submission #1007314

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1007314	2024-06-24T15:26:07 Z	DON_F	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	165 ms	17096 KB

jobs

#include <bits/stdc++.h>

using namespace std;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, d, m;
    cin >> n >> d >> m;
    vector<pair<int, int>> a(m);
    for (int i = 0; i < m; ++i){
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin(), a.end());
	auto Work = [&](int num){
		int j = 0;
		for (int day = 1; day <= n; ++day){
		    int k = 0;
		    while (j < m && k < num && day >= a[j].first){
				if (day > a[j].first + d){
					return false;
				}
				++j;
				++k;
			}
		}
		return (j == m);
	};
	int lo = 1, hi = m, ans = -1;
	while (lo <= hi){
		int mid = lo + (hi - lo) / 2;
		if (Work(mid)){
			ans = mid;
			hi = mid - 1;
		}else{
			lo = mid + 1;
		}
	}
    cout << ans << "\n";
    int j = 0;
    for (int i = 1; i <= n; ++i){
		int k = 0;
	    while (j < m && k < ans && i >= a[j].first){
			cout << a[j].second + 1 << " ";
			++j;
			++k;
		}
		cout << "0\n";
	}
	/*
	8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4
	*/
} 

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	2140 KB	Output is correct
2	Correct	12 ms	2140 KB	Output is correct
3	Correct	12 ms	2140 KB	Output is correct
4	Correct	12 ms	2128 KB	Output is correct
5	Correct	11 ms	2140 KB	Output is correct
6	Correct	12 ms	2140 KB	Output is correct
7	Correct	11 ms	2136 KB	Output is correct
8	Correct	15 ms	2136 KB	Output is correct
9	Correct	25 ms	2264 KB	Output is correct
10	Correct	19 ms	2128 KB	Output is correct
11	Correct	17 ms	2140 KB	Output is correct
12	Correct	37 ms	4068 KB	Output is correct
13	Correct	55 ms	5840 KB	Output is correct
14	Correct	75 ms	8016 KB	Output is correct
15	Correct	92 ms	9552 KB	Output is correct
16	Correct	115 ms	12116 KB	Output is correct
17	Correct	137 ms	13904 KB	Output is correct
18	Correct	151 ms	15124 KB	Output is correct
19	Correct	165 ms	17096 KB	Output is correct
20	Correct	148 ms	14104 KB	Output is correct