oj.uz

Submission #705313

# Submission time Handle Problem Language Result Execution time Memory
705313 2023-03-03T22:56:29 Z hanlulu Job Scheduling (CEOI12_jobs) C++14
100 / 100
 235 ms 14580 KB 
//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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1984 KB Output is correct
2 Correct 17 ms 1924 KB Output is correct
3 Correct 17 ms 2004 KB Output is correct
4 Correct 18 ms 1920 KB Output is correct
5 Correct 17 ms 2004 KB Output is correct
6 Correct 18 ms 2004 KB Output is correct
7 Correct 18 ms 1996 KB Output is correct
8 Correct 17 ms 1952 KB Output is correct
9 Correct 33 ms 2104 KB Output is correct
10 Correct 31 ms 2124 KB Output is correct
11 Correct 25 ms 1996 KB Output is correct
12 Correct 53 ms 3796 KB Output is correct
13 Correct 73 ms 5196 KB Output is correct
14 Correct 106 ms 6788 KB Output is correct
15 Correct 127 ms 8268 KB Output is correct
16 Correct 152 ms 9724 KB Output is correct
17 Correct 181 ms 11272 KB Output is correct
18 Correct 200 ms 12708 KB Output is correct
19 Correct 235 ms 14580 KB Output is correct
20 Correct 181 ms 11304 KB Output is correct