Submission #775753

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
775753	2023-07-06T21:16:05 Z	NK_	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	68 ms	26908 KB

jobs

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


int d[10];
int read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		ch = getchar();
	}
	int v = 0;
	while ('0' <= ch && ch <= '9') {
		v = v * 10 + (int) (ch - '0');
		ch = getchar();
	}
	return v;
}
 
void write(int x, bool newline) {
	int len = 0;
	while (x > 0) {
		d[len++] = x % 10;
		x /= 10;
	}
	for (int i = len - 1; i >= 0; i--) {
		putchar('0' + d[i]);
	}
	if (len == 0) {
		putchar('0');
	}
	if (newline) putchar('\n');
	else putchar(' ');
}

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

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

	function<bool(int, bool)> check = [&](int x, bool CREATE) {
		int cur = 0, len = 0;
		for(int i = 0; i < N; i++) {
			if (cur < len && in[cur].first <= i) return false;

			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 = 1, hi = M;
	while(lo < hi) {
		int mid = (lo + hi) / 2;
		if (check(mid, false)) hi = mid;
		else lo = mid + 1;
	}

	check(lo, 1);

	write(lo, true);
	for(int i = 0; i < N; i++) {
		for(auto &x : ans[i]) write(x + 1, 0);
		write(0, 1);
	}

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	7380 KB	Output is correct
2	Correct	8 ms	7380 KB	Output is correct
3	Correct	7 ms	7380 KB	Output is correct
4	Correct	7 ms	7380 KB	Output is correct
5	Correct	8 ms	7380 KB	Output is correct
6	Correct	7 ms	7380 KB	Output is correct
7	Correct	7 ms	7380 KB	Output is correct
8	Correct	7 ms	7380 KB	Output is correct
9	Correct	10 ms	7636 KB	Output is correct
10	Correct	14 ms	7612 KB	Output is correct
11	Correct	9 ms	7448 KB	Output is correct
12	Correct	15 ms	9940 KB	Output is correct
13	Correct	23 ms	13652 KB	Output is correct
14	Correct	39 ms	16164 KB	Output is correct
15	Correct	34 ms	17084 KB	Output is correct
16	Correct	53 ms	20044 KB	Output is correct
17	Correct	66 ms	25496 KB	Output is correct
18	Correct	54 ms	25348 KB	Output is correct
19	Correct	68 ms	26908 KB	Output is correct
20	Correct	66 ms	25432 KB	Output is correct