oj.uz

Submission #1085589

# Submission time Handle Problem Language Result Execution time Memory
1085589 2024-09-08T13:03:58 Z EntityPlantt Job Scheduling (CEOI12_jobs) C++17
70 / 100
 1000 ms 10580 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, 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:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   36 |  int l = 0, r = m, ans;
      |                    ^~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 2608 KB Output is correct
2 Correct 212 ms 2644 KB Output is correct
3 Correct 214 ms 2576 KB Output is correct
4 Correct 216 ms 2620 KB Output is correct
5 Correct 220 ms 2640 KB Output is correct
6 Correct 213 ms 2640 KB Output is correct
7 Correct 215 ms 2640 KB Output is correct
8 Correct 212 ms 2672 KB Output is correct
9 Correct 227 ms 2816 KB Output is correct
10 Correct 235 ms 2864 KB Output is correct
11 Correct 224 ms 2640 KB Output is correct
12 Correct 466 ms 5112 KB Output is correct
13 Correct 665 ms 7416 KB Output is correct
14 Correct 938 ms 10228 KB Output is correct
15 Execution timed out 1082 ms 8712 KB Time limit exceeded
16 Execution timed out 1006 ms 9812 KB Time limit exceeded
17 Execution timed out 1077 ms 8788 KB Time limit exceeded
18 Execution timed out 1047 ms 9808 KB Time limit exceeded
19 Execution timed out 1072 ms 10580 KB Time limit exceeded
20 Execution timed out 1044 ms 8492 KB Time limit exceeded