Submission #978951

#	Time	Username	Problem	Language	Result	Execution time	Memory
978951		Amaarsaa	Job Scheduling (CEOI12_jobs)	C++14	90 / 100	234 ms	18004 KiB

jobs

#include<bits/stdc++.h>

using namespace std;
using ll = long long ;
int a[100004] = {0}, n, d;
vector < ll > v[100004];
bool can(int mid) {
	int i, s;
	priority_queue < pair <int,int> , vector<pair<int,int>>, greater<pair<int,int>> > pq;
	for (i = 1; i <= n; i ++) {
		s = mid;
		pq.push({i + d, a[i]});
		while (s > 0) {
			if ( pq.empty()) break;
			pair <int,int> P = pq.top();
			pq.pop();
			if ( P.first < i) return 0;
			if ( s >= P.second) {
				s -= P.second;
			}
			else {
				P.second -= s;
				s= 0;
				pq.push(P);
			}
		}
	}
	if ( pq.empty()) return 1;
	return 0;
} 
void Ans(int mid) {
	int i, s;
	priority_queue < pair <int,int> , vector<pair<int,int>>, greater<pair<int,int>> > pq;
	for (i = 1; i <= n; i ++) {
		s = mid;
		pq.push({i + d, a[i]});
		while (s > 0) {
			if ( pq.empty()) break;
			pair <int,int> P = pq.top();
			pq.pop();
			if ( s >= P.second) {
				for (int j = 0; j < P.second; j ++) {
					
					cout << v[P.first - d].back() << " ";
					v[P.first - d].pop_back();
				}
				s -= P.second;
			}
			else {
				for (int j = 0; j < s; j ++) {
					
					cout << v[P.first - d].back() << " ";
					v[P.first - d].pop_back();
				}
				P.second -= s;
				s = 0;
				pq.push(P);
			}
		}
		cout << 0 << endl;
	}
	return ;
}
int main() {
//	freopen("moocast.in", "r", stdin);
//	freopen("moocast.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int m, i,x, lo, hi, mid;
	
	cin >> n >> d >> m;
	
	for (i = 1; i <= m; i ++) {
		cin >> x;
		v[x].push_back(i);
		a[x] ++;
	}
	
	lo = 1;
	hi = m; 
	while (lo < hi) {
		mid = (lo + hi)/2;
		if ( !
		can(mid)) lo = mid + 1;
		else hi = mid;
	}
	cout << lo   << endl;
	Ans(lo );
}

• Subtask 1: 90 / 100