Submission #705313

#	Time	Username	Problem	Language	Result	Execution time	Memory
705313		hanlulu	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	235 ms	14580 KiB

jobs

//https://oj.uz/problem/view/CEOI12_jobs?locale=en
#include <bits/stdc++.h>
using namespace std;
#define maxn 100001
const int MOD = 1e9+7;
/*just use binary to try the required machine number.
ween find number, loop array find the arrangement */
void setio()
{
	ios::sync_with_stdio(0);
	cin.tie(0);	
	cout.tie(0);
} 

int n,d,m;
vector<pair<int,int>> jobs;//first days, second: orginal id

bool isok(int x) {//each day can process x jobs.
	int j = 0;//current job.
	for (int i = 1; i <= n; i++) 
	{
		//the i-th day need process left jobs from previous days then current days.
		//if can not finish, leave it
		int cnt = x;
		while (j < m && jobs[j].first <= i && cnt > 0) {
			if (i - jobs[j].first > d) return false;
			j++;  
			cnt --;
		}
	}
	
	return j == m;
}
int main() {
	setio();
 	//freopen("hps.in","r",stdin);
 	//freopen("hps.out","w",stdout);
 	cin >> n >> d >> m;
 	jobs = vector<pair<int,int>>(m);
 	for (int i = 0; i < m; i++) 
	{
	 	cin >> jobs[i].first;
		jobs[i].second = i+1;	
	}
 	sort(jobs.begin(),jobs.end());
 	int l = 1, r = m;
 	int mid;
 	int ans;
 	while (l <= r) {
 		mid = (l+r)/2;
 		if (isok(mid)) {
 			ans = mid;
 			r = mid -1;
		}
		else l = mid+1;
	}

	cout << ans << '\n';
	
	//got ans, find arrangement 	
	int j = 0;//current job.
	for (int i = 1; i <= n; i++) 
	{
		int cnt = ans;
		while (j < m && jobs[j].first <= i && cnt > 0) {
			cout << jobs[j].second << " ";
			j++;  
			cnt --;
		}
		cout << 0 << '\n';
	}
		
	return 0;
}

Compilation message (stderr)

jobs.cpp: In function 'int main()':
jobs.cpp:48:7: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   48 |   int ans;
      |       ^~~

• Subtask 1: 100 / 100