Submission #132224

#	Time	Username	Problem	Language	Result	Execution time	Memory
132224		amoo_safar	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	195 ms	20236 KiB

jobs

#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int Maxn = 1e5 + 10;

vector<int> rec[Maxn], op[Maxn];
int cnt[Maxn];

int n, m, d;

bool check(int c){
	for(int i = 1; i <= n; i++) cnt[i] = rec[i].size();
	int p = 1, done = 0, free, rem;
	for(int i = 1; i <= n; i++){
		p = max(p, i - d);
		free = c;
		while((p <= i) && (free)){
			rem = min(free, cnt[p]);
			free -= rem;
			cnt[p] -= rem;
			done += rem;
			if(cnt[p] == 0) p++;
		}
	}
	return (done == m);
}

void solve(int c){
	int p = 1, free;
	for(int i = 1; i <= n; i++){
		p = max(p, i - d);
		free = c;
		while((p <= i) && (free)){
			if(rec[p].size() == 0){
				p ++;
				continue;
			}
			free --;
			op[i].pb(rec[p].back());
			rec[p].pop_back();
		}
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	int v;
	for(int i = 1; i <= m; i++){
		cin >> v;
		rec[v].pb(i);
	}
	int l = 0, r = m, mid;
	while(l + 1 < r){
		mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	solve(r);
	for(int i = 1; i <= n; i++){
		for(auto x : op[i]) cout << x << " ";
		cout << "0\n";
	}
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

• Subtask 1: 100 / 100