Submission #619680

#	Time	Username	Problem	Language	Result	Execution time	Memory
619680		gmsong	Job Scheduling (CEOI12_jobs)	C++11	0 / 100	317 ms	10924 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 < n; i++){
	// 	if(schedule[i].size() != 0){
	// 		for(int j = 0; j < schedule[i].size(); j++){
	// 			cout << schedule[i][j] << " ";
	// 		}
	// 	}
	// 	cout << 0 << endl;
	// }
}

• Subtask 1: 0 / 100