Submission #746569

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
746569	2023-05-22T19:34:22 Z	hasan_tawsif	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	418 ms	26572 KB

jobs

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

void solve() {
	int n, d, m; cin >> n >> d >> m;
	vector<pair<int, int > > v;
	for (int i = 0; i < m; ++i) {
		int x; cin >> x;
		v.push_back({x, i + 1});
	}
	sort(v.begin(), v.end());
	// for (auto [u, x] : v) cerr << u << " " << x << endl;
	// cerr << "----------------------------------------------\n";
	int lo = 1, hi = m;
	vector<int> ans[n + 1], final[n + 1];
	auto test = [&] (int numOfMachine) {
		for (int i = 1; i <= n; ++i) ans[i].clear();
		int cur = 0, tot = 0, day = 0;
		for (int i = 0; i < m; ) {
			int j = i;
			if (day < v[i].first) cur = 0;
			day = max(day, v[i].first);
			while (j < m and v[i].first == v[j].first) {
				if (day - v[j].first > d) return false;
				ans[day].push_back(v[j].second);
				cur++;
				tot++;
				j++;
	//			if (numOfMachine == 2) cerr << "#" << day << " " << tot << " " << cur << endl;
				if (cur == numOfMachine) cur = 0, day++;
			}
			i = j;
		}
		return tot == m;
	};
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (test(mid)) {
			hi = mid;
			for (int i = 1; i <= n; ++i) {
				final[i].clear();
				for (auto u : ans[i]) final[i].push_back(u);
			}
		}
		else lo = mid + 1;
	}
	cout << hi << "\n";
	for (int i = 1; i <= n; ++i) {
		for (auto u : final[i]) cout << u << " ";
		cout << 0 << "\n";
	}
} 

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1; 
//    cin >> t;
    while(t--) solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	3452 KB	Output is correct
2	Correct	37 ms	3468 KB	Output is correct
3	Correct	33 ms	3536 KB	Output is correct
4	Correct	38 ms	3532 KB	Output is correct
5	Correct	29 ms	3468 KB	Output is correct
6	Correct	27 ms	3444 KB	Output is correct
7	Correct	28 ms	3452 KB	Output is correct
8	Correct	28 ms	3536 KB	Output is correct
9	Correct	52 ms	7896 KB	Output is correct
10	Correct	58 ms	7912 KB	Output is correct
11	Correct	41 ms	3144 KB	Output is correct
12	Correct	84 ms	5592 KB	Output is correct
13	Correct	110 ms	8968 KB	Output is correct
14	Correct	179 ms	12412 KB	Output is correct
15	Correct	212 ms	13572 KB	Output is correct
16	Correct	295 ms	17536 KB	Output is correct
17	Correct	320 ms	22084 KB	Output is correct
18	Correct	351 ms	20768 KB	Output is correct
19	Correct	418 ms	26572 KB	Output is correct
20	Correct	310 ms	22064 KB	Output is correct