Submission #670909

#	Time	Username	Problem	Language	Result	Execution time	Memory
670909		canhnam357	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	284 ms	21432 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("angry.in", "r", stdin);
	//freopen("angry.out", "w", stdout);
	int n, d, m;
	cin >> n >> d >> m;
	vector<pair<int, int>> v(m);
	for (int i = 0; i < m; i++)
	{
		cin >> v[i].first;
		v[i].first += d;
		v[i].second = i + 1;
	}
	sort(v.begin(), v.end());
	int l = 0, r = m + 1;
	auto can = [&](int mid)
	{
		int pos = 0;
		for (int i = 1; pos < m; i++)
		{
			if (v[pos].first < i) return false;
			for (int j = 0; j < mid && pos < m; j++)
			{
				if (v[pos].first - d <= i && v[pos].first >= i) pos++;
				else break;
			}
		}
		return true;
	};
	while (r - l > 1)
	{
		int mid = (l + r) >> 1;
		if (can(mid)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	int pos = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < r && pos < m; j++)
		{
			if (v[pos].first - d <= i && v[pos].first >= i) pos++, cout << v[pos - 1].second << ' ';
			else break;
		}
		cout << 0 << '\n';
	}
	return 0;
}

• Subtask 1: 100 / 100