oj.uz

답안 #522056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522056 2022-02-03T16:36:25 Z alexz1205 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 283 ms 14416 KB 
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, d, m;
	cin >> n >> d >> m;
	vector<int> jobs[n];
	for (int x = 0; x < m; x ++){
		int a;
		cin >> a;
		jobs[a-1].push_back(x);
	}
	int lo = 0, hi = m;
	while (lo <= hi){
		int mid = lo + (hi-lo+1)/2;
		int c = 0;
		bool pos = true;
		vector<int> nums;
		for (int x = 0; x < n; x ++){
			c += jobs[x].size();
			c -= mid;
			c = max(0, c);
			if (c > d*mid){
				pos = false;
				break;
			}
		}
		if (pos){
			hi = mid-1;
		}else {
			lo = mid+1;
		}
	}
	int k = hi+1, c = 0;
	cout << k << endl;
	vector<int> stack;
	for (int x = 0; x < n; x ++){
		stack.insert(stack.begin(), jobs[x].begin(), jobs[x].end());
		c += jobs[x].size();
		for (int y = 0; y < min(c, k); y ++){
			cout << stack.back()+1 << " ";
			stack.pop_back();
		}
		c -= k;
		c = max(0, c);
		cout << "0\n";
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2236 KB Output is correct
2 Correct 28 ms 2340 KB Output is correct
3 Correct 32 ms 2244 KB Output is correct
4 Correct 25 ms 2292 KB Output is correct
5 Correct 25 ms 2364 KB Output is correct
6 Correct 26 ms 2236 KB Output is correct
7 Correct 26 ms 2236 KB Output is correct
8 Correct 31 ms 2364 KB Output is correct
9 Correct 39 ms 4380 KB Output is correct
10 Correct 34 ms 4352 KB Output is correct
11 Correct 29 ms 1844 KB Output is correct
12 Correct 64 ms 3572 KB Output is correct
13 Correct 95 ms 5444 KB Output is correct
14 Correct 167 ms 7032 KB Output is correct
15 Correct 146 ms 7536 KB Output is correct
16 Correct 221 ms 9584 KB Output is correct
17 Correct 254 ms 11388 KB Output is correct
18 Correct 232 ms 11576 KB Output is correct
19 Correct 283 ms 14416 KB Output is correct
20 Correct 241 ms 11408 KB Output is correct