Submission #1085586

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085586		vjudge1	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	197 ms	17236 KiB

jobs

#include <iostream>
#include <algorithm>
using namespace std;

const int M = 1e6 + 1, N = 100001;
int m, n, d;
pair <int, int> job[M];

template <bool write> bool simulate(int maxMachines) {
	int i = 0, j = 0;
	for (int day = 1; day <= n; day++) {
		if (write) cout << '\n';
		int machinesLeft = maxMachines;
		while (j < m && job[j].first == day) j++;
		while (i < j && machinesLeft) {
			if (job[i].first + d < day) return false;
			machinesLeft--;
			if (write) cout << job[i].second << ' ';
			i++;
		}
		if (write) cout << 0;
	}
	return true;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		cin >> job[i].first;
		job[i].second = i + 1;
	}
	sort(job, job + m);
	// for (int i = 0; i < m; i++) cerr << job[i].second << '\n';
	int l = 0, r = m, ans;
	while (l <= r) {
		int mid = l + r >> 1;
		if (simulate<false>(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans;
	simulate<true>(ans);
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
jobs.cpp:36:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |  int l = 0, r = m, ans;
      |                    ^~~

• Subtask 1: 100 / 100