Submission #1279041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279041		IBory	Job Scheduling (CEOI12_jobs)	C++20	100 / 100	168 ms	15944 KiB

jobs

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007;
vector<int> S[MAX], X[MAX];

bool Check(int Z, int N, int D) {
	for (int i = 1; i <= N; ++i) {
		X[i].clear();
		X[i].shrink_to_fit();
	}

	queue<pii> Q;
	for (int i = 1; i <= N; ++i) {
		for (int n : S[i]) Q.emplace(i + D, n);
		int t = min(Z, (int)Q.size());
		while (t--) {
			auto [d, id] = Q.front(); Q.pop();
			if (d < i) return 0;
			X[i].push_back(id);
		}
	}

	return Q.empty();
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, D, M;
	cin >> N >> D >> M;
	for (int i = 1; i <= M; ++i) {
		int n;
		cin >> n;
		S[n].push_back(i);
	}

	int L = 0, R = M;
	while (L + 1 < R) {
		int mid = (L + R) >> 1;
		(Check(mid, N, D) ? R : L) = mid;
	}

	Check(R, N, D);
	cout << R << '\n';
	for (int i = 1; i <= N; ++i) {
		for (int n : X[i]) cout << n << ' ';
		cout << 0 << '\n';
	}
	return 0;
}

• Subtask 1: 100 / 100