oj.uz

Submission #775749

# Submission time Handle Problem Language Result Execution time Memory
775749 2023-07-06T21:09:37 Z NK_ Job Scheduling (CEOI12_jobs) C++17
100 / 100
 136 ms 26884 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 MX = 1e6+6;
const int nax = 1e5+5;

pair<int, int> in[MX];
V<int> C[nax], ans[nax];

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

	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};

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

		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 14 ms 7480 KB Output is correct
2 Correct 14 ms 7380 KB Output is correct
3 Correct 16 ms 7448 KB Output is correct
4 Correct 16 ms 7380 KB Output is correct
5 Correct 14 ms 7368 KB Output is correct
6 Correct 15 ms 7428 KB Output is correct
7 Correct 15 ms 7380 KB Output is correct
8 Correct 19 ms 7480 KB Output is correct
9 Correct 21 ms 7620 KB Output is correct
10 Correct 20 ms 7584 KB Output is correct
11 Correct 17 ms 7444 KB Output is correct
12 Correct 30 ms 9908 KB Output is correct
13 Correct 41 ms 13504 KB Output is correct
14 Correct 66 ms 16156 KB Output is correct
15 Correct 64 ms 17100 KB Output is correct
16 Correct 95 ms 20060 KB Output is correct
17 Correct 115 ms 25396 KB Output is correct
18 Correct 107 ms 25360 KB Output is correct
19 Correct 136 ms 26884 KB Output is correct
20 Correct 124 ms 25436 KB Output is correct