Submission #1179468

#TimeUsernameProblemLanguageResultExecution timeMemory
1179468TsaganaJob Scheduling (CEOI12_jobs)C++20
100 / 100
89 ms7492 KiB
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define int long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

vector<int> a;
int n, d, m;


bool check(int mid) {
	int i = 1, j = 1;
	for(; i <= n && j <= m; i++) {
		if (i > a[j] + d) break ;
		int k = mid;
		while (j <= m && a[j] <= i && k--) j++;
	}
	return j > m;
}

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

void print(int k) {
	cout << k << '\n';
	for (int i = 1; i <= n; i++) cout << "0\n";
}

void solve () {
	cin >> n >> d >> m;
	a = vector<int>(m+1);
	for (int i = 1; i <= m; i++) {
		cin >> a[i];
	}
	sort(all(a));
	int k = search(1, m);
	print(k);
}
signed main() {IOS solve(); return 0;}
#Verdict Execution timeMemoryGrader output
Fetching results...