oj.uz

Submission #1085531

# Submission time Handle Problem Language Result Execution time Memory
1085531 2024-09-08T11:42:49 Z EntityPlantt Job Scheduling (CEOI12_jobs) C++17
20 / 100
 1000 ms 10632 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 215 ms 3668 KB Output isn't correct
2 Incorrect 208 ms 3728 KB Output isn't correct
3 Incorrect 253 ms 3796 KB Output isn't correct
4 Incorrect 232 ms 3664 KB Output isn't correct
5 Incorrect 231 ms 3792 KB Output isn't correct
6 Incorrect 210 ms 3664 KB Output isn't correct
7 Incorrect 216 ms 3652 KB Output isn't correct
8 Incorrect 212 ms 3668 KB Output isn't correct
9 Incorrect 219 ms 3832 KB Output isn't correct
10 Incorrect 215 ms 4020 KB Output isn't correct
11 Correct 239 ms 3688 KB Output is correct
12 Correct 517 ms 5068 KB Output is correct
13 Correct 656 ms 8700 KB Output is correct
14 Correct 953 ms 10068 KB Output is correct
15 Execution timed out 1055 ms 7744 KB Time limit exceeded
16 Execution timed out 1077 ms 9828 KB Time limit exceeded
17 Execution timed out 1051 ms 10048 KB Time limit exceeded
18 Execution timed out 1100 ms 9964 KB Time limit exceeded
19 Execution timed out 1048 ms 10632 KB Time limit exceeded
20 Execution timed out 1044 ms 9976 KB Time limit exceeded