oj.uz

답안 #409400

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
409400 2021-05-20T16:23:11 Z jairRS Job Scheduling (CEOI12_jobs) C++17
100 / 100
 257 ms 17352 KB 
#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

# 결과 실행 시간 메모리 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