Submission #496173

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
496173	2021-12-20T22:13:08 Z	aryan12	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	239 ms	24252 KB

jobs

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

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() {
	int n, d, m;
	cin >> n >> d >> m;
	vector<pair<int, int> > a(m + 1);
	for(int i = 1; i <= m; i++) {
		cin >> a[i].first;
		a[i].second = i;
	}
	sort(a.begin() + 1, a.end());
	a[0] = {-1, -1};
	int l = 1, r = m;
	int mid, ans = r + 1;
	while(l <= r) {
		mid = (l + r) >> 1;
		int cur_day = a[1].first, cur_cnt = 0, f = 0;
		for(int i = 1; i <= m; i++) {
			if(cur_cnt == mid) {
				cur_day++;
				cur_cnt = 0;
			}
			if(a[i].first > cur_day) {
				cur_day = a[i].first;
				cur_cnt = 0;
			}
			if(cur_day - a[i].first > d) {
				f = 1;
				break;
			}
			cur_cnt++;
		}
		if(f == 1) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
			ans = mid;
		}
	}
	cout << ans << "\n";
	int pos = 1;
	for(int i = 0; i < n; i++) {
		int cur_cnt = 0;
		while(pos != m + 1 && a[pos].first <= i + 1 && cur_cnt != ans) {
			cur_cnt++;
			cout << a[pos++].second << " ";
		}
		cout << "0\n";
	}
}

int32_t main() {
	auto begin = std::chrono::high_resolution_clock::now();
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	2760 KB	Output is correct
2	Correct	17 ms	2760 KB	Output is correct
3	Correct	18 ms	2772 KB	Output is correct
4	Correct	18 ms	2768 KB	Output is correct
5	Correct	17 ms	2760 KB	Output is correct
6	Correct	18 ms	2772 KB	Output is correct
7	Correct	17 ms	2760 KB	Output is correct
8	Correct	18 ms	2684 KB	Output is correct
9	Correct	29 ms	2896 KB	Output is correct
10	Correct	27 ms	2888 KB	Output is correct
11	Correct	24 ms	2768 KB	Output is correct
12	Correct	54 ms	5476 KB	Output is correct
13	Correct	83 ms	8196 KB	Output is correct
14	Correct	108 ms	11168 KB	Output is correct
15	Correct	127 ms	13380 KB	Output is correct
16	Correct	157 ms	16664 KB	Output is correct
17	Correct	185 ms	19548 KB	Output is correct
18	Correct	218 ms	21396 KB	Output is correct
19	Correct	239 ms	24252 KB	Output is correct
20	Correct	199 ms	19452 KB	Output is correct