Submission #703289

#	Time	Username	Problem	Language	Result	Execution time	Memory
703289		TAhmed33	Job Scheduling (CEOI12_jobs)	C++98	0 / 100	497 ms	13732 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
int n, d, m;
pair <int, int> arr[1000001] = {};
bool check (int x) {
	int pos = 1;
	int days = 0;
	while (pos <= m) {
		pair <int, int> dd = arr[pos];
		dd.F += d;
		int new_pos = upper_bound(arr + 1, arr + m + 1, dd) - arr;
		new_pos--;
		new_pos = min(new_pos, m);
		new_pos = min(new_pos, pos + x - 1);
		days++;
		pos = new_pos + 1;
	}
	return (days <= n);
}
void build (int x) {
	int pos = 1;
	int days = 0;
	while (pos <= m) {
		pair <int, int> dd = arr[pos];
		dd.F += d;
		int new_pos = upper_bound(arr + 1, arr + m + 1, dd) - arr;
		new_pos--;
		new_pos = min(new_pos, m);
		new_pos = min(new_pos, pos + x - 1);
		days++;
		for (int i = pos; i <= new_pos; i++) cout << arr[i].S << " ";
		cout << 0 << endl;
		pos = new_pos + 1;
	}
	while (days <= n) {
		cout << 0 << endl;
		days++;
	}
}
int main () {
	cin >> n >> d >> m;
	for (int i = 1; i <= m; i++) {
		cin >> arr[i].F;
		arr[i].S = i;
	}
	sort(arr + 1, arr + m + 1);
	int l = 1, r = m;
	int mid, ans = m;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) {
			r = mid - 1;
			ans = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << ans << endl;
	build(ans);
}

• Subtask 1: 0 / 100