Submission #522038

#	Time	Username	Problem	Language	Result	Execution time	Memory
522038		alexz1205	Job Scheduling (CEOI12_jobs)	C++14	50 / 100	261 ms	13672 KiB

jobs

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, d, m;
	cin >> n >> d >> m;
	vector<int> jobs[n];
	for (int x = 0; x < m; x ++){
		int a;
		cin >> a;
		jobs[a-1].push_back(x);
	}
	int lo = 0, hi = m;
	while (lo <= hi){
		int mid = lo + (hi-lo+1)/2;
		int c = 0;
		bool pos = true;
		vector<int> nums;
		for (int x = 0; x < n; x ++){
			c += jobs[x].size();
			c -= mid;
			c = max(0, c);
			if (c >= d*mid){
				pos = false;
				break;
			}
		}
		if (pos){
			hi = mid-1;
		}else {
			lo = mid+1;
		}
	}
	int k = hi+1, c = 0;
	cout << k << endl;
	vector<int> stack;
	for (int x = 0; x < n; x ++){
		stack.insert(stack.begin(), jobs[x].begin(), jobs[x].end());
		c += jobs[x].size();
		for (int y = 0; y < min(c, k); y ++){
			cout << stack.back()+1 << " ";
			stack.pop_back();
		}
		c -= k;
		c = max(0, c);
		cout << "0\n";
	}
	return 0;
}

• Subtask 1: 50 / 100