Submission #810856

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810856	2023-08-06T16:47:33 Z	khanghb2006	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	198 ms	20724 KB

jobs

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define MASK(n) (1 << (n))
#define BIT(mask,x) ((mask >> (x)) & 1)
#define TASK "task"

using namespace std;
const int mxN = 1e6 + 7;
const int base = 512;
const int inf = 1e9 + 6969;
const int Mod = 1e9 + 7;
const long long infll = 1e18 + 6969;

template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
     if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
     if (a < b) {a = b; return true;} return false;
}

#define int long long

int n;
int d;
int m;
pair<int,int>a[mxN];

bool ok(int num_machine) {
	int j = 1;
	int cnt;
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		if(a[j].fi + d < i) {
			//cout << i << " " << j << "\n";
			return false;
		}
		while(cnt < num_machine && a[j].fi <= i && j <= m) {
			cnt++; 
			j++;
		}
		if(j > m) return true;
	}
	return false;
}

void tracing(int num_machine) {
	int j = 1;
	int cnt;
	for (int i = 1; i <= n; i++) {
		cnt = 0;
		while(cnt < num_machine && a[j].fi <= i && j <= m) {
			cnt++;
			cout << a[j].se << " ";
			j++;
		}
		cout << 0 << '\n';
	}
}

void solve() {
	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);
	int lo = 1,hi = max(n,m),ans = 0;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(ok(mid)) {
			ans = mid;
			hi = mid - 1;
		}else lo = mid + 1;
	}
	cout << ans << "\n";
	tracing(ans);
}

signed main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--) {
		solve();
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2388 KB	Output is correct
2	Correct	13 ms	2388 KB	Output is correct
3	Correct	13 ms	2380 KB	Output is correct
4	Correct	13 ms	2412 KB	Output is correct
5	Correct	13 ms	2388 KB	Output is correct
6	Correct	13 ms	2388 KB	Output is correct
7	Correct	13 ms	2472 KB	Output is correct
8	Correct	15 ms	2516 KB	Output is correct
9	Correct	24 ms	2652 KB	Output is correct
10	Correct	24 ms	2568 KB	Output is correct
11	Correct	20 ms	2496 KB	Output is correct
12	Correct	40 ms	4728 KB	Output is correct
13	Correct	60 ms	6964 KB	Output is correct
14	Correct	89 ms	9260 KB	Output is correct
15	Correct	101 ms	11460 KB	Output is correct
16	Correct	131 ms	13764 KB	Output is correct
17	Correct	152 ms	16220 KB	Output is correct
18	Correct	172 ms	18344 KB	Output is correct
19	Correct	198 ms	20724 KB	Output is correct
20	Correct	154 ms	16084 KB	Output is correct