oj.uz

Submission #1085540

# Submission time Handle Problem Language Result Execution time Memory
1085540 2024-09-08T11:48:57 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
70 / 100
 1000 ms 10484 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 213 ms 3664 KB Output is correct
2 Correct 212 ms 3868 KB Output is correct
3 Correct 215 ms 3664 KB Output is correct
4 Correct 218 ms 3852 KB Output is correct
5 Correct 212 ms 3668 KB Output is correct
6 Correct 211 ms 3968 KB Output is correct
7 Correct 221 ms 3736 KB Output is correct
8 Correct 211 ms 3664 KB Output is correct
9 Correct 225 ms 3988 KB Output is correct
10 Correct 227 ms 3928 KB Output is correct
11 Correct 220 ms 3668 KB Output is correct
12 Correct 441 ms 5108 KB Output is correct
13 Correct 671 ms 8528 KB Output is correct
14 Correct 896 ms 10092 KB Output is correct
15 Execution timed out 1008 ms 7652 KB Time limit exceeded
16 Execution timed out 1062 ms 9812 KB Time limit exceeded
17 Execution timed out 1066 ms 9844 KB Time limit exceeded
18 Execution timed out 1070 ms 9856 KB Time limit exceeded
19 Execution timed out 1063 ms 10484 KB Time limit exceeded
20 Execution timed out 1086 ms 10012 KB Time limit exceeded