Submission #703256

#	Time	Username	Problem	Language	Result	Execution time	Memory
703256		bachtg	Job Scheduling (CEOI12_jobs)	C++17	45 / 100	214 ms	13656 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> s;

bool f(int m) {
	int l = 0, r = m - 1;
	// m = 3 => 3 machine 
	//
	int day = 1;
	while (r < M) {
		while (l <= r) {
			if (a[l].first < day) return false;
			l++;
		}
		day++;
		r += m;
	}
	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].first += K;
		a[i].second = i + 1;
	}
	sort(all(a));

	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';

	int L = 0, R = r - 1;
	int num = 0;
	while (R < M) {
		int b = 0;
		while (L <= R) {
			cout << a[L].second << " ";
			b++;
			L++;
		}
		while (b < r) cout << "0 ";
		cout << "0\n";
		num++;
		R += r;
	}
	while (num < N) {
		cout << "0\n";
		num++;
	}

	return 0;
}

• Subtask 1: 45 / 100