Submission #892720

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
892720	2023-12-25T18:05:35 Z	bashNewbie	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	225 ms	28620 KB

jobs

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define pb push_back
template <typename T> using vt = vector<T>;
using vi = vt<int>;
using vvi = vt<vi>;

int main() {
	fast_io;

	int n, d, m; cin >> n >> d >> m;
	vi job(m); vvi in(n);
	for(int j = 0; j < m; j++) {
		int x; cin >> x, --x;
		job[j] = x, in[x].pb(j);
	}
	vi ord;
	for(int i = 0; i < n; i++) for(int x: in[i]) ord.pb(x);

	vvi day;
	auto proc = [&] (int N) {
		day = vvi(n);
		int cur = 0, l = 0;
		while(l < m) {
			int f = N;
			while(l < m && f > 0) {
				int on = job[ord[l]];
				if(on < cur-d) return 0;
				if(on > cur) break;
				day[cur].pb(ord[l]+1), ++l, --f;
			}
			++cur;
		}
		return 1;
	};

	int x = 0, y = m, z;
	while(x < y) {
		z = x+y >> 1;
		if(proc(z)) y = z; else
		x = z+1;
	}
	proc(x);

	cout << x << "\n";
	for(int i = 0; i < n; i++) {
		for(int x: day[i]) cout << x << " ";
		cout << "0\n";
	}
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:43:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   z = x+y >> 1;
      |       ~^~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	3344 KB	Output is correct
2	Correct	18 ms	3308 KB	Output is correct
3	Correct	18 ms	3340 KB	Output is correct
4	Correct	18 ms	3344 KB	Output is correct
5	Correct	18 ms	3344 KB	Output is correct
6	Correct	18 ms	3340 KB	Output is correct
7	Correct	21 ms	3340 KB	Output is correct
8	Correct	18 ms	3380 KB	Output is correct
9	Correct	27 ms	11804 KB	Output is correct
10	Correct	27 ms	12580 KB	Output is correct
11	Correct	21 ms	3028 KB	Output is correct
12	Correct	41 ms	5228 KB	Output is correct
13	Correct	63 ms	8904 KB	Output is correct
14	Correct	116 ms	12324 KB	Output is correct
15	Correct	106 ms	12632 KB	Output is correct
16	Correct	165 ms	18344 KB	Output is correct
17	Correct	194 ms	22432 KB	Output is correct
18	Correct	210 ms	21956 KB	Output is correct
19	Correct	225 ms	28620 KB	Output is correct
20	Correct	187 ms	21764 KB	Output is correct