oj.uz

Submission #1011888

# Submission time Handle Problem Language Result Execution time Memory
1011888 2024-07-01T10:37:24 Z belgianbot Job Scheduling (CEOI12_jobs) C++14
40 / 100
 270 ms 26756 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 = 0, 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 26 ms 3316 KB Output isn't correct
2 Incorrect 25 ms 3416 KB Output isn't correct
3 Incorrect 28 ms 3472 KB Output isn't correct
4 Incorrect 23 ms 3404 KB Output isn't correct
5 Incorrect 25 ms 3492 KB Output isn't correct
6 Incorrect 25 ms 3400 KB Output isn't correct
7 Incorrect 30 ms 3388 KB Output isn't correct
8 Incorrect 30 ms 3660 KB Output isn't correct
9 Incorrect 39 ms 9896 KB Output isn't correct
10 Incorrect 39 ms 9768 KB Output isn't correct
11 Correct 20 ms 2604 KB Output is correct
12 Correct 39 ms 4328 KB Output is correct
13 Correct 61 ms 7496 KB Output is correct
14 Correct 105 ms 10384 KB Output is correct
15 Correct 96 ms 9836 KB Output is correct
16 Correct 136 ms 13792 KB Output is correct
17 Correct 160 ms 18240 KB Output is correct
18 Incorrect 160 ms 19776 KB Output isn't correct
19 Incorrect 270 ms 26756 KB Output isn't correct
20 Correct 162 ms 19300 KB Output is correct