Submission #810853

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
810853	2023-08-06T16:44:40 Z	khanghb2006	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	103 ms	9420 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 = 5e5 + 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;
}

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

75.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	2004 KB	Output is correct
2	Correct	13 ms	1916 KB	Output is correct
3	Correct	15 ms	2004 KB	Output is correct
4	Correct	14 ms	1936 KB	Output is correct
5	Correct	13 ms	1988 KB	Output is correct
6	Correct	14 ms	2008 KB	Output is correct
7	Correct	13 ms	1924 KB	Output is correct
8	Correct	16 ms	1932 KB	Output is correct
9	Correct	25 ms	2128 KB	Output is correct
10	Correct	27 ms	2124 KB	Output is correct
11	Correct	21 ms	1972 KB	Output is correct
12	Correct	53 ms	3848 KB	Output is correct
13	Correct	61 ms	5736 KB	Output is correct
14	Correct	88 ms	8012 KB	Output is correct
15	Correct	103 ms	9420 KB	Output is correct
16	Incorrect	36 ms	6788 KB	Output isn't correct
17	Incorrect	30 ms	6716 KB	Output isn't correct
18	Incorrect	26 ms	6380 KB	Output isn't correct
19	Incorrect	31 ms	6508 KB	Output isn't correct
20	Incorrect	30 ms	6796 KB	Output isn't correct