Submission #892720

#	Time	Username	Problem	Language	Result	Execution time	Memory
892720		bashNewbie	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	225 ms	28620 KiB

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 (stderr)

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

• Subtask 1: 100 / 100