oj.uz

Submission #775745

# Submission time Handle Problem Language Result Execution time Memory
775745 2023-07-06T21:03:57 Z NK_ Job Scheduling (CEOI12_jobs) C++17
100 / 100
 236 ms 24988 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, D, M; cin >> N >> D >> M;
	V<V<int>> C(N); for(int i = 0; i < M; i++) {
		int t; cin >> t; --t;
		C[t].pb(i);
	}

	V<V<int>> ans(N);
	queue<pair<int, int>> in;
	auto check = [&](int x) -> bool {
		ans = V<V<int>>(N);
		in = {};

		for(int i = 0; i < N; i++) {
			if (sz(in) && in.front().first <= i) return 0;

			int end = i + D + 1;
			for(auto& c : C[i]) in.push(pair<int, int>{end, c});

			int left = x;
			while(left-- && sz(in)) {
				ans[i].push_back(in.front().second);
				in.pop();
			}
		}

		return sz(in) == 0;
	};

	int lo = 0, hi = M + 1;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid)) hi = mid;
		else lo = mid + 1;
	}

	check(lo);

	cout << lo << nl;
	for(int i = 0; i < N; i++) {
		for(auto x : ans[i]) cout << x + 1 << " ";
		cout << 0 << nl;
	}
	cout << nl;


    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3380 KB Output is correct
2 Correct 20 ms 3388 KB Output is correct
3 Correct 21 ms 3432 KB Output is correct
4 Correct 21 ms 3400 KB Output is correct
5 Correct 20 ms 3528 KB Output is correct
6 Correct 21 ms 3460 KB Output is correct
7 Correct 20 ms 3416 KB Output is correct
8 Correct 21 ms 3380 KB Output is correct
9 Correct 36 ms 11252 KB Output is correct
10 Correct 36 ms 11800 KB Output is correct
11 Correct 24 ms 2400 KB Output is correct
12 Correct 45 ms 4584 KB Output is correct
13 Correct 64 ms 7748 KB Output is correct
14 Correct 120 ms 11168 KB Output is correct
15 Correct 106 ms 10504 KB Output is correct
16 Correct 160 ms 14928 KB Output is correct
17 Correct 209 ms 19448 KB Output is correct
18 Correct 176 ms 17972 KB Output is correct
19 Correct 236 ms 24988 KB Output is correct
20 Correct 202 ms 19516 KB Output is correct