Submission #557650

#	Time	Username	Problem	Language	Result	Execution time	Memory
557650		Hanksburger	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	256 ms	17204 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
pair<int, int> b[1000005];
queue<pair<int, int> > q;
int a[100005];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, d, m, l=1, r=1e6, index=1;
	cin >> n >> d >> m;
	for (int i=1; i<=m; i++)
	{
		cin >> b[i].first;
		b[i].second=i;
		a[b[i].first]++;
	}
	sort(b+1, b+m+1);
	while (l<r)
	{
		int mid=(l+r)/2;
		bool ok=1;
		for (int i=1; i<=n; i++)
		{
			if (a[i])
				q.push({i, a[i]});
			int cnt=mid;
			while (q.size() && cnt>=q.front().second)
			{
				cnt-=q.front().second;
				q.pop();
			}
			if (q.size())
			{
				if (q.front().first<=i-d)
				{
					ok=0;
					break;
				}
				q.front().second-=cnt;
			}
		}
		if (ok)
			r=mid;
		else
			l=mid+1;
		while (q.size())
			q.pop();
	}
	cout << l << '\n';
	for (int i=1; i<=n; i++)
	{
		while (index<=m && b[index].first==i)
		{
			q.push({b[index].second, 0});
			index++;
		}
		int cnt=l;
		while (q.size() && cnt)
		{
			cout << q.front().first << ' ';
			cnt--;
			q.pop();
		}
		cout << 0 << '\n';
	}
	return 0;
}

• Subtask 1: 100 / 100