Submission #713911

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
713911	2023-03-23T08:12:28 Z	iskhakkutbilim	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	252 ms	13808 KB

jobs

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

#define ff first
#define ss second
#define all(a) a.begin(), a.end()


main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
   int n, m, k;
	cin >> n >> m >> k;
	vector<pair<int, int> > job(k);
	for(int i = 0;i < k; i++){
		cin >> job[i].ff;
		job[i].ss = i;
	}
	sort(all(job));
	function<int(int, int)> good=[&](int machine, int pr){
		int j = 0;
		for(int i = 1;i <= n; i++){
			int cnt = 0;
			while(cnt < machine && j < k){
				if(i < job[j].ff) break;
				if(i > job[j].ff + m) return 0;
				if(pr) cout << job[j].ss+1 << ' ';
				j++, cnt++;
			}
			if(pr) cout << 0 << '\n';	
		}
		if(j < k) return 0;
		return 1;
	};
	/*
	8 2 12
	1 2 4 2 1 3 5 6 2 3 6 4
	*/
	int l = 0, r = (int)2e6;
	while(l + 1 < r){
		int mid = (l + r)>>1;
		if(good(mid, 0)){
			r = mid;
		}else{
			l = mid;
		}
	}
	cout << r << '\n';
	if(!good(r, 0)) assert(false);
	good(r, 1);
	return 0;
}

Compilation message

jobs.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1620 KB	Output is correct
2	Correct	19 ms	1748 KB	Output is correct
3	Correct	20 ms	1620 KB	Output is correct
4	Correct	21 ms	1620 KB	Output is correct
5	Correct	26 ms	1620 KB	Output is correct
6	Correct	18 ms	1620 KB	Output is correct
7	Correct	18 ms	1628 KB	Output is correct
8	Correct	18 ms	1732 KB	Output is correct
9	Correct	32 ms	1820 KB	Output is correct
10	Correct	39 ms	1888 KB	Output is correct
11	Correct	24 ms	1620 KB	Output is correct
12	Correct	53 ms	3148 KB	Output is correct
13	Correct	85 ms	4576 KB	Output is correct
14	Correct	121 ms	6124 KB	Output is correct
15	Correct	128 ms	7612 KB	Output is correct
16	Correct	163 ms	9052 KB	Output is correct
17	Correct	195 ms	10536 KB	Output is correct
18	Correct	207 ms	12108 KB	Output is correct
19	Correct	252 ms	13808 KB	Output is correct
20	Correct	199 ms	10576 KB	Output is correct