Submission #775752

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
775752	2023-07-06T21:14:40 Z	NK_	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	82 ms	26868 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);
	}

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

	check(lo, 1);

	write(lo, 1);
	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	7 ms	7380 KB	Output is correct
2	Correct	7 ms	7380 KB	Output is correct
3	Correct	7 ms	7372 KB	Output is correct
4	Correct	8 ms	7372 KB	Output is correct
5	Correct	8 ms	7452 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	11 ms	7636 KB	Output is correct
11	Correct	9 ms	7464 KB	Output is correct
12	Correct	15 ms	9940 KB	Output is correct
13	Correct	22 ms	13600 KB	Output is correct
14	Correct	38 ms	16076 KB	Output is correct
15	Correct	35 ms	17140 KB	Output is correct
16	Correct	54 ms	20064 KB	Output is correct
17	Correct	82 ms	25492 KB	Output is correct
18	Correct	55 ms	25332 KB	Output is correct
19	Correct	64 ms	26868 KB	Output is correct
20	Correct	78 ms	25480 KB	Output is correct