oj.uz

Submission #746189

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

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

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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 1576 KB Time limit exceeded
2 Execution timed out 1072 ms 1612 KB Time limit exceeded
3 Execution timed out 1059 ms 1564 KB Time limit exceeded
4 Execution timed out 1079 ms 1516 KB Time limit exceeded
5 Execution timed out 1084 ms 1612 KB Time limit exceeded
6 Execution timed out 1082 ms 1616 KB Time limit exceeded
7 Execution timed out 1075 ms 1604 KB Time limit exceeded
8 Execution timed out 1074 ms 1612 KB Time limit exceeded
9 Runtime error 119 ms 65536 KB Execution killed with signal 9
10 Runtime error 98 ms 65536 KB Execution killed with signal 9
11 Execution timed out 1083 ms 1568 KB Time limit exceeded
12 Execution timed out 1072 ms 2288 KB Time limit exceeded
13 Execution timed out 1053 ms 3084 KB Time limit exceeded
14 Correct 163 ms 6612 KB Output is correct
15 Execution timed out 1086 ms 4136 KB Time limit exceeded
16 Execution timed out 1066 ms 5880 KB Time limit exceeded
17 Execution timed out 1082 ms 7548 KB Time limit exceeded
18 Correct 293 ms 11004 KB Output is correct
19 Runtime error 246 ms 65536 KB Execution killed with signal 9
20 Execution timed out 1084 ms 7484 KB Time limit exceeded