Submission #703273

#	Time	Username	Problem	Language	Result	Execution time	Memory
703273		bachtg	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	234 ms	23612 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 pos = 0;
	for (int day = 1; day <= N; ++day) {
		for (int j = 0; j < m; ++j) {
			if (a[pos].first > day) break;
			if (a[pos].first + K < day) return false;
			else pos++;
			if (pos == M) return true;
		}
	}
	return false;
}

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;
	}
	cout << r << "\n";
	vector<int> ans[N];
	int pos = 0;
	for (int day = 1; day <= N; ++day) {
		for (int j = 0; j < r; ++j) {
			if (a[pos].first > day) break;
			if (a[pos].first + K >= day) {
				ans[day - 1].push_back(a[pos++].second);
			}
			if (pos == M) break;
		}
		if (pos == M) break;
	} 

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

	return 0;
}

• Subtask 1: 100 / 100