oj.uz

답안 #468041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
468041 2021-08-26T06:33:19 Z clams Job Scheduling (CEOI12_jobs) C++17
100 / 100
 512 ms 26388 KB 
/*
 * Author: bubu2006
**/

#include <bits/stdc++.h>
using namespace std;

int n, d, m;
vector<pair<int, int>> req;
    
pair<bool, vector<vector<int>>> ok(int x) {
	vector<vector<int>> res(n);
	int aint = 0;
	for(int day = 1; day <= n; day++) {
		for(int j = 0; j < x; j++) {
			if(req[aint].first > day) {
				break;
			}
			
			if(req[aint].first + d >= day) {
				res[day - 1].push_back(req[aint++].second);
			} else {
				return {0, res};
			}
			
			if(aint == m) {
				return {1, res};
			}
		}
	}
	
	return {0, res};
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
	cin >> n >> d >> m;
	
	req.resize(m);
	for(int i = 0; i < m; i++) {
		cin >> req[i].first;
		req[i].second = i + 1;
	}
	
	sort(req.begin(), req.end());
	
	vector<vector<int>> ans;
	
	int l = 0;
	int r = m;
	
	while(l < r - 1) {
		int mid = l + (r - l) / 2;
		auto tmp = ok(mid);
		if(tmp.first) {
			r = mid;
			ans = tmp.second;
		} else {
			l = mid;
		}
	}
	
	cout << r << '\n';
	for(int i = 0; i < n; i++) {
		for(int j : ans[i]) {
			cout << j << ' ';
		}
		cout << 0 << '\n';
	}
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 2960 KB Output is correct
2 Correct 39 ms 2956 KB Output is correct
3 Correct 42 ms 2956 KB Output is correct
4 Correct 39 ms 3004 KB Output is correct
5 Correct 39 ms 2960 KB Output is correct
6 Correct 39 ms 3056 KB Output is correct
7 Correct 40 ms 2964 KB Output is correct
8 Correct 40 ms 3000 KB Output is correct
9 Correct 106 ms 9636 KB Output is correct
10 Correct 101 ms 9692 KB Output is correct
11 Correct 47 ms 2724 KB Output is correct
12 Correct 98 ms 4964 KB Output is correct
13 Correct 144 ms 8516 KB Output is correct
14 Correct 233 ms 10764 KB Output is correct
15 Correct 245 ms 11016 KB Output is correct
16 Correct 323 ms 15876 KB Output is correct
17 Correct 390 ms 18896 KB Output is correct
18 Correct 438 ms 18452 KB Output is correct
19 Correct 512 ms 26388 KB Output is correct
20 Correct 393 ms 19104 KB Output is correct