oj.uz

Submission #746190

# Submission time Handle Problem Language Result Execution time Memory
746190 2023-05-21T20:48:53 Z JellyTheOctopus Job Scheduling (CEOI12_jobs) C++17
20 / 100
 1000 ms 13996 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() {
	cin >> N >> D >> M;
	for (int i = 1; i <= M; i++) {
		int t;
		cin >> t;
		arr[t].push_back(i);
	}
	int high = N;
	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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 3756 KB Time limit exceeded
2 Execution timed out 1084 ms 3660 KB Time limit exceeded
3 Execution timed out 1079 ms 3684 KB Time limit exceeded
4 Execution timed out 1089 ms 3660 KB Time limit exceeded
5 Execution timed out 1074 ms 3652 KB Time limit exceeded
6 Execution timed out 1090 ms 3660 KB Time limit exceeded
7 Execution timed out 1085 ms 3660 KB Time limit exceeded
8 Execution timed out 1079 ms 3660 KB Time limit exceeded
9 Execution timed out 1063 ms 3556 KB Time limit exceeded
10 Correct 47 ms 4364 KB Output is correct
11 Execution timed out 1073 ms 3724 KB Time limit exceeded
12 Execution timed out 1018 ms 4428 KB Time limit exceeded
13 Execution timed out 1066 ms 5192 KB Time limit exceeded
14 Correct 169 ms 8336 KB Output is correct
15 Execution timed out 1089 ms 6080 KB Time limit exceeded
16 Execution timed out 1088 ms 7904 KB Time limit exceeded
17 Execution timed out 1079 ms 9640 KB Time limit exceeded
18 Correct 272 ms 12836 KB Output is correct
19 Correct 330 ms 13996 KB Output is correct
20 Execution timed out 1073 ms 9608 KB Time limit exceeded