Submission #619954

#	Time	Username	Problem	Language	Result	Execution time	Memory
619954		gmsong	Job Scheduling (CEOI12_jobs)	C++11	100 / 100	661 ms	20656 KiB

jobs

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

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

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

int a[100001];
bool possible(int machines){
	int day = 1;
	memset(a,0,sizeof(a));
	for(int i = 0; i < m; i++){
		int early = v[i].first;
		int late = v[i].first + d;
		day = early;
		while(a[day] >= machines){
			day++;
		}
		if(day > late){
			return 0;
		}
		a[day]++;
	}
	return 1;
}

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

	
	for(int i = 1; i <= m; i++){
		int val;
		cin >> val;
		v.push_back({val, i});
	}
	sort(v.begin(), v.end());
	// cout << possible(11) << endl;
	int lo = 1;
	int hi = m;
	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;
		}
	}

	cout << ans << endl;
	int day = 1;
	vector<int> schedule[100001];
	for(int i = 0; i < m; i++){
		int early = v[i].first;
		int late = v[i].first + d;
		day = early;
		while(schedule[day].size() >= ans){
			day++;
		}
		schedule[day].push_back(v[i].second);
	}
	
	for(int i = 1; i <= n; 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:62:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |   while(schedule[day].size() >= ans){
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~
jobs.cpp:60:7: warning: unused variable 'late' [-Wunused-variable]
   60 |   int late = v[i].first + d;
      |       ^~~~
jobs.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int j = 0; j < schedule[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100