oj.uz

Submission #1085529

# Submission time Handle Problem Language Result Execution time Memory
1085529 2024-09-08T11:39:06 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
20 / 100
 1000 ms 13908 KB 
#include <iostream>
#include <algorithm>
using namespace std;

const int M = 1e6 + 1, N = 100001;
int m, n, d;
pair <int, int> job[M];

template <bool write> bool simulate(int maxMachines) {
	int i = 0, j = 0;
	for (int day = 1; day <= n; day++) {
		if (write) cout << '\n';
		int machinesLeft = maxMachines;
		while (j < m && job[j].first == day) j++;
		while (i < j && machinesLeft) {
			if (job[i].first + d < day) return false;
			machinesLeft--;
			if (write) cout << job[i].second << ' ';
			i++;
		}
		if (write) cout << 0;
	}
	return true;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		cin >> job[i].first;
		job[i].second = i + 1;
	}
	sort(job, job + m);
	for (int i = 0; i < m; i++) cerr << job[i].second << '\n';
	int l = 0, r = m / n + 5, ans;
	while (l <= r) {
		int mid = l + r >> 1;
		if (simulate<false>(mid)) {
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans;
	simulate<true>(ans);
	return 0;
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid = l + r >> 1;
      |             ~~^~~
jobs.cpp:36:28: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |  int l = 0, r = m / n + 5, ans;
      |                            ^~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 217 ms 4272 KB Output isn't correct
2 Incorrect 209 ms 4076 KB Output isn't correct
3 Incorrect 226 ms 4088 KB Output isn't correct
4 Incorrect 220 ms 4180 KB Output isn't correct
5 Incorrect 221 ms 4056 KB Output isn't correct
6 Incorrect 208 ms 4040 KB Output isn't correct
7 Incorrect 223 ms 3924 KB Output isn't correct
8 Incorrect 209 ms 4028 KB Output isn't correct
9 Incorrect 233 ms 4176 KB Output isn't correct
10 Incorrect 218 ms 4188 KB Output isn't correct
11 Correct 223 ms 4180 KB Output is correct
12 Correct 460 ms 5932 KB Output is correct
13 Correct 660 ms 9840 KB Output is correct
14 Correct 887 ms 12004 KB Output is correct
15 Execution timed out 1038 ms 9808 KB Time limit exceeded
16 Execution timed out 1046 ms 12628 KB Time limit exceeded
17 Execution timed out 1029 ms 13160 KB Time limit exceeded
18 Execution timed out 1050 ms 12996 KB Time limit exceeded
19 Execution timed out 1068 ms 13908 KB Time limit exceeded
20 Execution timed out 1049 ms 12880 KB Time limit exceeded