Submission #619682

#	Time	Username	Problem	Language	Result	Execution time	Memory
619682		gmsong	Job Scheduling (CEOI12_jobs)	C++11	10 / 100	367 ms	17056 KiB

jobs

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int n, d, m;
vector<pair<int, int> > v;

vector<vector<int> > schedule(n);

bool possible(int machines){
	int i = 0;
	int curAmt = 0;
	int day = 1;
	while(i < m){
		curAmt++;
		// cout << "day is " << day << endl;
		// cout << "curAmt is " << curAmt << endl;
		// cout << "i is " << curAmt << endl;
		// cout << "v[i].first is " << v[i].first << endl;
		// cout << endl;
		if(v[i].first < day){
			return 0;
		}
		if(curAmt == machines){
			curAmt = 0;
			day++;
		}
		i++;
	}
	return 1;
}

int main() {
	cin >> n >> d >> m;

	
	for(int i = 1; i <= m; i++){
		int val;
		cin >> val;
		val += d;
		v.push_back({val, i});
	}
	sort(v.begin(), v.end());
	// cout << possible(11) << endl;
	int lo = 1;
	int hi = m + 10;
	int ans = 0;
	while(lo <= hi){
		int mid = (lo + hi)/2;
		// cout << "mid is " << mid << endl;
		if(possible(mid)){
			// cout << "worked" << endl;
			hi = mid - 1;
			ans = mid;
		}
		else{
			lo = mid + 1;
		}
	}
	// schedule[1 - 1].push_back(0);
	int i = 0;
	int curAmt = 0;
	int day = 1;
	vector<int> row;
	while(i < m){
		curAmt++;
		
		// cout << "day is " << day << endl;
		// cout << "curAmt is " << curAmt << endl;
		// cout << "i is " << curAmt << endl;
		// cout << "v[i].first is " << v[i].first << endl;
		// cout << endl;
		row.push_back(v[i].second);
		if(curAmt == ans){
			schedule.push_back(row);
			row.clear();
			curAmt = 0;
			day++;
		}
		i++;
	}
	// cout<< schedule[0].size() << endl;
	cout << ans << endl;
	for(int i = 0; i < schedule.size(); i++){
		for(int j = 0; j < schedule[i].size(); j++){
			cout << schedule[i][j] << " ";
		}
		cout << 0 << endl;
	}
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i = 0; i < schedule.size(); i++){
      |                 ~~^~~~~~~~~~~~~~~~~
jobs.cpp:86:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for(int j = 0; j < schedule[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 100