Submission #409400

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
409400	2021-05-20T16:23:11 Z	jairRS	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	257 ms	17352 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	1972 KB	Output is correct
2	Correct	25 ms	1928 KB	Output is correct
3	Correct	20 ms	1892 KB	Output is correct
4	Correct	20 ms	1996 KB	Output is correct
5	Correct	22 ms	1920 KB	Output is correct
6	Correct	20 ms	1996 KB	Output is correct
7	Correct	20 ms	1912 KB	Output is correct
8	Correct	19 ms	1996 KB	Output is correct
9	Correct	32 ms	4668 KB	Output is correct
10	Correct	30 ms	4728 KB	Output is correct
11	Correct	21 ms	1860 KB	Output is correct
12	Correct	42 ms	3376 KB	Output is correct
13	Correct	59 ms	5692 KB	Output is correct
14	Correct	257 ms	7820 KB	Output is correct
15	Correct	98 ms	8644 KB	Output is correct
16	Correct	134 ms	11472 KB	Output is correct
17	Correct	178 ms	13916 KB	Output is correct
18	Correct	156 ms	13588 KB	Output is correct
19	Correct	200 ms	17352 KB	Output is correct
20	Correct	179 ms	13892 KB	Output is correct