oj.uz

Submission #1011885

# Submission time Handle Problem Language Result Execution time Memory
1011885 2024-07-01T10:34:14 Z belgianbot Job Scheduling (CEOI12_jobs) C++14
40 / 100
 271 ms 25532 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> tasks;
int N, D, M;
vector<vector<int>> possible (int nbMachine) {
	queue <pair<int,int>> q;
	vector<vector<int>> ans(N);
	for (int i(0); i < N; i++) {
		if (!q.empty() && q.front().second - i >= D) return {};
		int sum = nbMachine;
		for (int x : tasks[i]) q.push({x, i});
		while (!q.empty() && sum > 0) {
			sum--;
			ans[i].push_back(q.front().first);
			q.pop();
		}
	}
	if (!q.empty()) return {};
	return ans;
}
		
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	cin >> N >> D >> M;
	tasks.resize(N);
	
	for (int i = 0; i < M; i++) {
		int a; cin >> a; a--;
		tasks[a].push_back(i);
	}
	
	int l = 1, r = 1000000;
	while (l < r) {
		int mid = r - (r - l) / 2;
		//cout << l << " " << r << '\n';
		
		if (possible(mid).empty()) l = mid;
		else r = mid - 1;
	}
	
	cout << l + 1 << '\n';
	vector<vector<int>> ans = possible(l + 1);
	for (auto x : ans) {
		for (int y : x) {
			cout << y + 1 << " ";
		}
		cout << "0\n";
	}
	
	return 0;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 3404 KB Output isn't correct
2 Incorrect 25 ms 3404 KB Output isn't correct
3 Incorrect 35 ms 3396 KB Output isn't correct
4 Incorrect 34 ms 3392 KB Output isn't correct
5 Incorrect 25 ms 3396 KB Output isn't correct
6 Incorrect 25 ms 3404 KB Output isn't correct
7 Incorrect 25 ms 3484 KB Output isn't correct
8 Incorrect 39 ms 3472 KB Output isn't correct
9 Incorrect 51 ms 8360 KB Output isn't correct
10 Incorrect 36 ms 8352 KB Output isn't correct
11 Correct 20 ms 2652 KB Output is correct
12 Correct 38 ms 4600 KB Output is correct
13 Correct 65 ms 7764 KB Output is correct
14 Correct 107 ms 10660 KB Output is correct
15 Correct 102 ms 10308 KB Output is correct
16 Correct 138 ms 14704 KB Output is correct
17 Correct 157 ms 19044 KB Output is correct
18 Incorrect 163 ms 18668 KB Output isn't correct
19 Incorrect 271 ms 25532 KB Output isn't correct
20 Correct 189 ms 18220 KB Output is correct