Submission #522396

#	Time	Username	Problem	Language	Result	Execution time	Memory
522396		Yazan_Alattar	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	494 ms	14344 KiB

jobs

#include <bits/stdc++.h>

using namespace std;
const int M = 1000005;
#define F first
#define S second

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

bool check(int mid)
{
	int pos = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= mid && pos <= m && a[pos].F <= i; ++j) if(i - a[pos++].F > d) return 0;
	return (pos == m + 1);
}

int main()
{
	cin >> n >> d >> m;
	for(int i = 1; i <= m; ++i) cin >> a[i].F, a[i].S = i;
	sort(a + 1, a + m + 1);
	int l = 1, r = m + 1;
	while(l < r){
		int mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r << endl;
	int pos = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= r && pos <= m && a[pos].F <= i; ++j, ++pos) cout << a[pos].S << " ";
		cout << 0 << endl;
	}
}

• Subtask 1: 100 / 100