Submission #703267

#	Time	Username	Problem	Language	Result	Execution time	Memory
703267		bachtg	Job Scheduling (CEOI12_jobs)	C++17	55 / 100	330 ms	23616 KiB

jobs

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ll long long
#define pii pair<int, int>
#define soclose 1e-9

int N, K, M;
vector<pii> a;
vector<int> b;

bool f(int m) {
	int day = 1;
	for (int i = 0; i < M; ++i) {
		b[i] = day;
		if ((i + 1) % m == 0) day++; 
	}
	for (int i = 0; i < M; ++i) {
		if (a[i].first + K < b[i]) return false;
	}
	return true;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//freopen("angry.in", "r", stdin);
	//freopen("angry.out", "w", stdout);
	cin >> N >> K >> M;

	a.resize(M);
	for (int i = 0; i < M; ++i) {
		cin >> a[i].first;
		a[i].second = i + 1;
	}
	sort(all(a));
	b.assign(M, 0);

	int l = 0, r = M;
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (f(m)) r = m;
		else l = m;
	}
	
	vector<int> ans[N];
	int day = 0;
	for (int i = 0; i < M; ++i) {
		ans[day].push_back(a[i].second);
		if ((i + 1) % r == 0) day++;
	}
	cout << r << '\n';
	for (int i = 0; i < N; ++i) {
		for (int x : ans[i]) cout << x << " ";
		cout << "0\n";
	}

	return 0;
}

• Subtask 1: 55 / 100