Submission #409400

#	Time	Username	Problem	Language	Result	Execution time	Memory
409400		jairRS	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	257 ms	17352 KiB

jobs

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int n, d, m, a;
vvi dayIndexes;

bool check(int machines){
	vi available(n + 1, machines);
	for (int i = 1; i <= n - d; i++)
	{
		int jobs = dayIndexes[i].size();
		for (int j = i; j <= i + d; j++)
		{
			if(available[j] >= jobs){
				available[j] -= jobs;
				jobs = 0;
			} else {
				jobs -= available[j];
				available[j] = 0;
			}
		}
		if(jobs) return false;
	}
	return true;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> d >> m;
	dayIndexes = vvi(n + 1);
	for (int i = 1; i <= m; i++)
	{
		cin >> a;
		dayIndexes[a].pb(i);
	}

	ll lo = 1, hi = 1000000;
	while(lo <= hi){
		ll mid = (lo + hi)/2;

		if(check(mid)) hi = mid - 1;
		else lo = mid + 1;
	}
	
	cout << lo << '\n';
	int curday = 1;
	for (int i = 1; i <= n; i++)
	{
		int machines = lo;
		while(machines--){
			while(curday <= n && dayIndexes[curday].empty()) curday++;
			if(curday > n) break;
			cout << dayIndexes[curday].back() << " ";
			dayIndexes[curday].pop_back();
		}
		cout << "0\n";
	}
}

• Subtask 1: 100 / 100