oj.uz

Submission #775750

# Submission time Handle Problem Language Result Execution time Memory
775750 2023-07-06T21:10:00 Z NK_ Job Scheduling (CEOI12_jobs) C++17
100 / 100
 127 ms 26960 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 7380 KB Output is correct
2 Correct 15 ms 7380 KB Output is correct
3 Correct 15 ms 7380 KB Output is correct
4 Correct 15 ms 7360 KB Output is correct
5 Correct 14 ms 7456 KB Output is correct
6 Correct 17 ms 7400 KB Output is correct
7 Correct 17 ms 7360 KB Output is correct
8 Correct 14 ms 7380 KB Output is correct
9 Correct 20 ms 7680 KB Output is correct
10 Correct 20 ms 7564 KB Output is correct
11 Correct 15 ms 7504 KB Output is correct
12 Correct 28 ms 9804 KB Output is correct
13 Correct 47 ms 13508 KB Output is correct
14 Correct 68 ms 16168 KB Output is correct
15 Correct 69 ms 17096 KB Output is correct
16 Correct 95 ms 20040 KB Output is correct
17 Correct 113 ms 25420 KB Output is correct
18 Correct 106 ms 25376 KB Output is correct
19 Correct 127 ms 26960 KB Output is correct
20 Correct 113 ms 25396 KB Output is correct