oj.uz

Submission #746191

# Submission time Handle Problem Language Result Execution time Memory
746191 2023-05-21T20:51:00 Z JellyTheOctopus Job Scheduling (CEOI12_jobs) C++17
20 / 100
 1000 ms 13552 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 = 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 1085 ms 3412 KB Time limit exceeded
2 Execution timed out 1067 ms 3412 KB Time limit exceeded
3 Execution timed out 1076 ms 3412 KB Time limit exceeded
4 Execution timed out 1076 ms 3412 KB Time limit exceeded
5 Execution timed out 1085 ms 3412 KB Time limit exceeded
6 Execution timed out 1080 ms 3412 KB Time limit exceeded
7 Execution timed out 1072 ms 3468 KB Time limit exceeded
8 Execution timed out 1081 ms 3540 KB Time limit exceeded
9 Execution timed out 1073 ms 3412 KB Time limit exceeded
10 Correct 35 ms 4184 KB Output is correct
11 Execution timed out 1084 ms 3412 KB Time limit exceeded
12 Execution timed out 1088 ms 3924 KB Time limit exceeded
13 Execution timed out 1078 ms 4852 KB Time limit exceeded
14 Correct 99 ms 8240 KB Output is correct
15 Execution timed out 1082 ms 5596 KB Time limit exceeded
16 Execution timed out 1087 ms 7508 KB Time limit exceeded
17 Execution timed out 1076 ms 9036 KB Time limit exceeded
18 Correct 166 ms 12716 KB Output is correct
19 Correct 201 ms 13552 KB Output is correct
20 Execution timed out 1082 ms 9092 KB Time limit exceeded