oj.uz

Submission #746192

# Submission time Handle Problem Language Result Execution time Memory
746192 2023-05-21T20:51:59 Z JellyTheOctopus Job Scheduling (CEOI12_jobs) C++17
25 / 100
 1000 ms 13516 KB 
#include <bits/stdc++.h>
using namespace std;

int N, D, M;
vector<int> arr[100001];

bool check(int x) {
	queue<int> q;
	int wait = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < (int)arr[i].size(); j++) {
			q.push(i);
		}
		if (!q.empty()) {
			wait = max(wait, i-q.front());
		}
		for (int j = 0; j < x && !q.empty(); j++) {
			q.pop();
		}
	}
	return wait <= D;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> N >> D >> M;
	for (int i = 1; i <= M; i++) {
		int t;
		cin >> t;
		arr[t].push_back(i);
	}
	int high = M;
	int low = 0;
	while (low < high) {
		int mid = (high+low)/2;
		if (check(mid)) {
			high = mid-1;
		}
		else {
			low = mid;
		}
	}
	int ans = high+1;
	cout << ans << "\n";
	queue<int> q;
	for (int i = 1; i <= N; i++) {
		for (auto v: arr[i]) {
			q.push(v);
		}
		for (int j = 0; j < ans && !q.empty(); j++) {
			cout << q.front() << ' ';
			q.pop();
		}
		cout << 0 << '\n';
	}	
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 3412 KB Time limit exceeded
2 Execution timed out 1084 ms 3412 KB Time limit exceeded
3 Execution timed out 1088 ms 3412 KB Time limit exceeded
4 Execution timed out 1081 ms 3412 KB Time limit exceeded
5 Execution timed out 1086 ms 3412 KB Time limit exceeded
6 Execution timed out 1082 ms 3412 KB Time limit exceeded
7 Execution timed out 1086 ms 3412 KB Time limit exceeded
8 Execution timed out 1083 ms 3412 KB Time limit exceeded
9 Execution timed out 1082 ms 3284 KB Time limit exceeded
10 Correct 33 ms 4172 KB Output is correct
11 Execution timed out 1088 ms 3156 KB Time limit exceeded
12 Execution timed out 1094 ms 3668 KB Time limit exceeded
13 Correct 68 ms 6880 KB Output is correct
14 Execution timed out 1089 ms 6012 KB Time limit exceeded
15 Correct 110 ms 9044 KB Output is correct
16 Execution timed out 1090 ms 7648 KB Time limit exceeded
17 Execution timed out 1087 ms 8964 KB Time limit exceeded
18 Correct 180 ms 12672 KB Output is correct
19 Correct 206 ms 13516 KB Output is correct
20 Execution timed out 1082 ms 9016 KB Time limit exceeded