Submission #392588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
392588	2021-04-21T10:52:29 Z	huukhang	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	291 ms	13892 KB

jobs

// - Only when necessary :d
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define fileopen(a, b) freopen(((string)a + ".inp").c_str(), "r", stdin); freopen(((string)b + ".out").c_str(), "w", stdout); 

#define ll long long
// #define int long long
#define fi first
#define se second
#define pb push_back
typedef pair<int, int> pii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll mod = 1e9 + 7;
const ll inf = 1e9 + 7;
const double eps = 1e-9;

int n, d, m;
pii a[1000005];
int l, r, mid, ans;

bool check(int x) {
	int res = -inf;
	int j = 1, last = 1;
	for (int i = 1; i <= n; ++i) {
		while (j <= m && a[j].fi <= i && j - last < x) {
			res = max(res, i - a[j].fi);
			++j;
		}
		last = j;
	}

	return res <= d;
}

void trace(int x) {
	int j = 1, last = 1;
	for (int i = 1; i <= n; ++i) {
		while (j <= m && a[j].fi <= i && j - last < x) {
			cout << a[j].se << " ";
			++j;
		}
		cout << "0\n";
		last = j;
	}
}

signed main() {
	#ifdef khangorz
		fileopen("input", "output");
	#endif
	#ifndef khangorz
//		fileopen("LAH", "LAH");
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	for (int i = 1; i <= m; ++i) {
		cin >> a[i].fi;
		a[i].se = i;
	}
	sort(a + 1, a + m + 1);

	l = 1; r = 1000000; mid = l + (r - l)/2;
	while (l <= r) {
		if (check(mid)) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}

		mid = l + (r - l)/2;
	}

	cout << ans << "\n";
	trace(ans);
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	22 ms	1740 KB	Output is correct
2	Correct	22 ms	1760 KB	Output is correct
3	Correct	22 ms	1740 KB	Output is correct
4	Correct	22 ms	1728 KB	Output is correct
5	Correct	22 ms	1860 KB	Output is correct
6	Correct	22 ms	1780 KB	Output is correct
7	Correct	22 ms	1740 KB	Output is correct
8	Correct	22 ms	1704 KB	Output is correct
9	Correct	36 ms	1988 KB	Output is correct
10	Correct	35 ms	1976 KB	Output is correct
11	Correct	31 ms	1720 KB	Output is correct
12	Correct	61 ms	3264 KB	Output is correct
13	Correct	97 ms	4676 KB	Output is correct
14	Correct	130 ms	6180 KB	Output is correct
15	Correct	154 ms	7748 KB	Output is correct
16	Correct	193 ms	9156 KB	Output is correct
17	Correct	230 ms	10748 KB	Output is correct
18	Correct	253 ms	12200 KB	Output is correct
19	Correct	291 ms	13892 KB	Output is correct
20	Correct	228 ms	10764 KB	Output is correct