Submission #899446

#	Time	Username	Problem	Language	Result	Execution time	Memory
899446		MongHwa	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	187 ms	16724 KiB

jobs

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

#define X first
#define Y second

pair<int, int> arr[1000001];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, d, m;
	cin >> n >> d >> m;

	for(int i = 0; i < m; i++)
	{
		cin >> arr[i].X;
		arr[i].Y = i+1;
	}

	sort(arr, arr+m);

	int l = 0, r = m;
	while(l < r)
	{
		int mid = (l+r) / 2;

		int pos = 0, i = 0;
		bool ok = 1;
		for(int days = 1; days <= n && ok; days++)
		{
			for(i = pos; i < pos+mid && i < m; i++)
			{
				if(arr[i].X > days)
					break;
				if(arr[i].X + d < days)
				{
					ok = 0;
					break;
				}
			}

			pos = i;
			if(pos == m)
				break;
		}

		if(ok && pos == m)
			r = mid;
		else
			l = mid+1;
	}

	cout << l << '\n';
	int pos = 0, i = 0;
	for(int days = 1; days <= n; days++)
	{
		for(i = pos; i < pos+l && i < m; i++)
		{
			if(arr[i].X <= days)
				cout << arr[i].Y << ' ';
			else
				break;
		}

		cout << "0\n";
		pos = i;
		if(pos == m)
			continue;
	}
}

• Subtask 1: 100 / 100