oj.uz

Submission #974787

# Submission time Handle Problem Language Result Execution time Memory
974787 2024-05-03T19:16:43 Z vjudge1 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 425 ms 17408 KB 
#include<iostream>
#include<algorithm>
using namespace std;

int n, d, m; // avalible days, max delay, job count
pair<int, int> arrive[1000001]; // when the jobs come in

bool isok(int machines) {
	int current = 0;
	for (int i = 1; i <= n; i++) {
		int machines_left = machines;
		while (machines_left > 0 && current < m && arrive[i].first <= i) {
			if (i - arrive[i].first >= d) {
				return false;
			}

			machines_left--;
			current++;
		}
	}

	return current == m; // can complete all jobs
}

int main() {
	cin >> n >> d >> m;
	for (int i = 0; i < m; i++) {
		cin >> arrive[i].first;
		arrive[i].second = i + 1;
	}

	sort(arrive, arrive + m);

	int left = 1, right = m;
	int ans = 1;

	while (left <= right) {
		int mid = (left + right) / 2; // bsearch for how many machines needed
		if (isok(mid)) {
			ans = mid;
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}

	int current = 0;
	for (int i = 1; i <= n; i++) {
		int machines_left = ans;
		while (machines_left > 0 && current < m && arrive[i].first <= i) {
			cout << arrive[current].second << " ";

			machines_left--;
			current++;
		}

		cout << 0 << endl;
	}
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 3416 KB Output isn't correct
2 Incorrect 33 ms 3416 KB Output isn't correct
3 Incorrect 38 ms 3548 KB Output isn't correct
4 Incorrect 35 ms 3412 KB Output isn't correct
5 Incorrect 33 ms 3420 KB Output isn't correct
6 Incorrect 33 ms 3416 KB Output isn't correct
7 Incorrect 33 ms 3420 KB Output isn't correct
8 Incorrect 34 ms 3420 KB Output isn't correct
9 Incorrect 140 ms 3512 KB Expected EOLN
10 Incorrect 146 ms 3684 KB Expected EOLN
11 Incorrect 34 ms 3556 KB Expected EOLN
12 Incorrect 69 ms 4688 KB Expected EOLN
13 Incorrect 104 ms 7628 KB Expected EOLN
14 Incorrect 145 ms 9168 KB Expected EOLN
15 Incorrect 172 ms 10192 KB Expected EOLN
16 Incorrect 213 ms 13648 KB Expected EOLN
17 Incorrect 276 ms 14928 KB Expected EOLN
18 Incorrect 261 ms 15172 KB Expected EOLN
19 Incorrect 425 ms 17408 KB Expected EOLN
20 Incorrect 257 ms 14928 KB Expected EOLN