oj.uz

Submission #416421

# Submission time Handle Problem Language Result Execution time Memory
416421 2021-06-02T11:18:46 Z shubham20_03 Job Scheduling (CEOI12_jobs) C++17
0 / 100
 347 ms 26784 KB 
#include <bits/stdc++.h>
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
#define int long long
#define deb1(x) cout << #x << "=" << x << endl;
#define deb2(x, y) cout << #x << "=" << x << ", " << #y << "=" << y << endl;
#define ff first
#define ss second
#define pb push_back

int N, D, M;
pair<int, int> a[1000300];
vector<int> ans_dur;

bool ok(int m) {
	int cm = 0, cd = 1;
	ans_dur.clear();

	for (int i = 1; i <= M; i++) {
		if (cm < m) {
			if (a[i].ff > cd) {
				cm = 1, cd = a[i].ff;
				ans_dur.pb(0); ans_dur.pb(a[i].ss);
			}
			else {
				cm++;
				ans_dur.pb(a[i].ss);
				if (cd - a[i].ff > D)
					return 0;
			}
		}
		else {
			cm = 1, cd++;
			ans_dur.pb(0); ans_dur.pb(a[i].ss);
			if (cd - a[i].ff > D)
				return 0;
		}
	}

	ans_dur.pb(0);
	return 1;
}

void show() {
	for (int x : ans_dur) {
		cout << x << " ";
		if (x == 0) cout << "\n";
	}
}

signed main() {
	FAST;

	cin >> N >> D >> M;
	for (int i = 1; i <= M; i++) {
		cin >> a[i].ff;
		a[i].ss = i;
	}
	sort(a + 1, a + 1 + M);

	int l = 1, r = M, ans = M;
	while (l <= r) {
		int m = l + (r - l) / 2;
		if (ok(m)) ans = m, r = m - 1;
		else l = m + 1;
	}
	cout << ans << endl;
	show();
	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3320 KB Expected EOLN
2 Incorrect 30 ms 3288 KB Expected EOLN
3 Incorrect 26 ms 3332 KB Expected EOLN
4 Incorrect 28 ms 3324 KB Expected EOLN
5 Incorrect 28 ms 3332 KB Expected EOLN
6 Incorrect 32 ms 3312 KB Expected EOLN
7 Incorrect 32 ms 3288 KB Expected EOLN
8 Incorrect 34 ms 3328 KB Expected EOLN
9 Incorrect 39 ms 3308 KB Expected EOLN
10 Incorrect 44 ms 3284 KB Expected EOLN
11 Incorrect 39 ms 3392 KB Expected EOLN
12 Incorrect 79 ms 6444 KB Expected EOLN
13 Incorrect 114 ms 9468 KB Expected EOLN
14 Incorrect 155 ms 12620 KB Expected EOLN
15 Incorrect 211 ms 15528 KB Expected EOLN
16 Incorrect 229 ms 18664 KB Expected EOLN
17 Incorrect 284 ms 21772 KB Expected EOLN
18 Incorrect 325 ms 24776 KB Expected EOLN
19 Incorrect 347 ms 26784 KB Expected EOLN
20 Incorrect 279 ms 21708 KB Expected EOLN