Submission #711367

#	Time	Username	Problem	Language	Result	Execution time	Memory
711367		xyzxyz	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	246 ms	13900 KiB

jobs

#include <bits/stdc++.h>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, d, m;
	cin >> n >> d >> m;
	vector<int> requests(n);
	vector<vector<int>> auftrage(n);
	int upper = 0, lower = 1;
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> a;
		a--;
		requests[a]++;
		auftrage[a].push_back(i);
		upper = max(upper, requests[a]);
	}
	//cout << d << endl;
	while(upper-lower>0){
		int maschinen = (lower+upper)/2;
		//cout << maschinen << endl;
		int last = 0, rest = requests[0];
		bool pos = true;
		for(int i=0; i<n && pos; i++){
			if (i - last > d) {
				//cout << i << "-" << last << ">" << d << "false" << endl;
				pos = false;
			}
			int tmp = maschinen;
			while(tmp>0 && last<=i){
				int tmp2 = min(rest, tmp);
				tmp -= tmp2;
				rest -= tmp2;
				if(rest == 0 && last<=i){
					last++;
					rest = requests[last];
				}
			}
		}
		if(pos){
			//cout << maschinen << endl;
			upper = maschinen;
		} 
		else lower = maschinen+1;
	}
	cout << lower << endl;
	int curr = 0;
	int j = auftrage[curr].size()-1;
	for (int b = 0; b < n; b++) {
		for (int i = 0; i < lower && b >= curr && curr < auftrage.size() && j >= 0; i++) {
			cout << auftrage[curr][j] << " ";
			j--;
			if (j < 0) {
				curr++;
				if(curr < auftrage.size()) j = auftrage[curr].size()-1;
			}
		}
		cout << 0 << endl;
	}

	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:53:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0; i < lower && b >= curr && curr < auftrage.size() && j >= 0; i++) {
      |                                             ~~~~~^~~~~~~~~~~~~~~~~
jobs.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     if(curr < auftrage.size()) j = auftrage[curr].size()-1;
      |        ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100