oj.uz

Submission #775747

# Submission time Handle Problem Language Result Execution time Memory
775747 2023-07-06T21:06:55 Z NK_ Job Scheduling (CEOI12_jobs) C++17
100 / 100
 132 ms 26896 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>;

const int nax = 1e6+6;
pair<int, int> in[nax];

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);
	auto check = [&](int x, bool CREATE = 0) -> bool {

		int cur = 0, len = 0;
		for(int i = 0; i < N; i++) {
			if (cur < len && in[cur].first <= i) return 0;

			int end = i + D + 1;
			for(auto& c : C[i]) in[len++] = {end, c};

			int left = x;
			while(left-- && cur < len) {
				if (CREATE) ans[i].push_back(in[cur].second);
				cur++;
			}
		}

		return cur == len;
	};

	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, 1);

	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 13 ms 3208 KB Output is correct
2 Correct 13 ms 3188 KB Output is correct
3 Correct 13 ms 3144 KB Output is correct
4 Correct 14 ms 3236 KB Output is correct
5 Correct 16 ms 3224 KB Output is correct
6 Correct 13 ms 3156 KB Output is correct
7 Correct 14 ms 3140 KB Output is correct
8 Correct 13 ms 3228 KB Output is correct
9 Correct 21 ms 7636 KB Output is correct
10 Correct 21 ms 7616 KB Output is correct
11 Correct 14 ms 2772 KB Output is correct
12 Correct 28 ms 5216 KB Output is correct
13 Correct 45 ms 8884 KB Output is correct
14 Correct 68 ms 11908 KB Output is correct
15 Correct 67 ms 12496 KB Output is correct
16 Correct 122 ms 15820 KB Output is correct
17 Correct 127 ms 21292 KB Output is correct
18 Correct 111 ms 21064 KB Output is correct
19 Correct 132 ms 26896 KB Output is correct
20 Correct 119 ms 21292 KB Output is correct