Submission #132239

#	Time	Username	Problem	Language	Result	Execution time	Memory
132239		Atalasion	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	654 ms	23356 KiB

jobs

#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()
#define F first 
#define S second

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef string str;

const ll MOD = 1e9 + 7;
const ll N = 1e6 + 10;
const ll INF = 1e18;

ll n, d, m;

pll a[N];

bool isval(ll x){
	queue <pll> q;
	ll pnt = 1;
	//cout << x << '\n';
	for (int i = 1; i <= n; i++){
		if (pnt != m + 1){
			while ((pnt != m + 1) && (a[pnt].F == i)) q.push(a[pnt]), pnt ++;
		}
		//cout << i << ' ' << pnt << ' ' << q.size() << ' ' << x << ' ';
		for (int j = 0; j < x; j++){
		    if (q.size() == 0) break;
		    q.pop();
		}
		//cout << q.size() << '\n';
		if (q.size() != 0){
			if (q.front().F + d < i + 1){
				return 0;
			}
		}
	}
	if (q.size()) return 0;
	return 1;
}


int main(){
	cin >> n >> d >> m;
	for (int i = 1; i <= m; i++){
		ll v;
		cin >> v;
		a[i] = {v, i};
	}
	sort(a + 1, a + m + 1);
	ll l = 0, r = n;
	while (r - l > 1){
		ll mid = (l + r) / 2;
		//cout << l << ' ' << r << '\n';
		if (isval(mid)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	ll x = r;
	queue <pll> q;
	ll pnt = 1;
	for (int i = 1; i <= n; i++){
		if (pnt != m + 1){
			while ((pnt != m + 1) && (a[pnt].F == i)) q.push(a[pnt]), pnt ++;
		}
		//cout << i << ' ' << pnt << ' ' << q.size() << ' ' << x << ' ';
		for (int j = 0; j < x; j++){
		    if (q.size() == 0) break;
			cout << q.front().S << ' ';
		    q.pop();
		}
		cout << 0 << '\n';
		//cout << q.size() << '\n';
		if (q.size() != 0){
			if (q.front().F + d < i + 1){
				return 0;
			}
		}
	}
	
	
	
	
	
	
	return 0;
}
	/*8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4*/
	
	

• Subtask 1: 60 / 100