Submission #810853

#	Time	Username	Problem	Language	Result	Execution time	Memory
810853		khanghb2006	Job Scheduling (CEOI12_jobs)	C++17	75 / 100	103 ms	9420 KiB

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 / 100