oj.uz

답안 #670425

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
670425 2022-12-09T01:47:08 Z asdf334 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 253 ms 17648 KB 
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int N, D, M; cin >> N >> D >> M;
	map<int, vector<int>> vals;
	for (int i = 1; i <= M; ++i) {
		int num; cin >> num;
		vals[num].push_back(i);
	}
	int left = 1; int right = 1e6;
	while (left < right) {
		int mid = left + (right - left) / 2;
		int day = 1; int curr = 0; int del = 0;
		for (auto val : vals) {
			if (day < val.first) {
				day = val.first; curr = 0;
			}
			for (int i = 0; i < sz(val.second); ++i) {
				if (curr < mid) {
					++curr; 
				} else {
					++day; curr = 1;
				}
				del = max(del, day - val.first);
			}
		} 
		if (del > D) {
			left = mid + 1;
		} else {
			right = mid;
		}
	}
	cout << left << '\n';
	int ctr = 0; vector<vector<int>> ans(N);
	for (auto val : vals) {
		for (int num : val.second) {
			if (sz(ans[ctr]) >= left) ++ctr;
			ans[ctr].push_back(num);
		}
	}
	for (vector<int> day : ans) {
		for (int req : day) {
			cout << req << " ";
		}
		cout << 0 << '\n';
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 2508 KB Output is correct
2 Correct 19 ms 2508 KB Output is correct
3 Correct 18 ms 2616 KB Output is correct
4 Correct 17 ms 2612 KB Output is correct
5 Correct 18 ms 2572 KB Output is correct
6 Correct 17 ms 2636 KB Output is correct
7 Correct 17 ms 2596 KB Output is correct
8 Correct 19 ms 2544 KB Output is correct
9 Correct 25 ms 4628 KB Output is correct
10 Correct 25 ms 4664 KB Output is correct
11 Correct 25 ms 2132 KB Output is correct
12 Correct 47 ms 3736 KB Output is correct
13 Correct 76 ms 6628 KB Output is correct
14 Correct 145 ms 9680 KB Output is correct
15 Correct 119 ms 8624 KB Output is correct
16 Correct 211 ms 12044 KB Output is correct
17 Correct 239 ms 16716 KB Output is correct
18 Correct 184 ms 14764 KB Output is correct
19 Correct 216 ms 17648 KB Output is correct
20 Correct 253 ms 16764 KB Output is correct