Submission #713902

#	Time	Username	Problem	Language	Result	Execution time	Memory
713902		iskhakkutbilim	Job Scheduling (CEOI12_jobs)	C++14	35 / 100	243 ms	13752 KiB

jobs

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

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

int n, m, k;
vector<pair<int, int> > job;



main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	job.resize(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;
			if(i > n-m){
				if(pr) cout << 0 << '\n';
			}else{
				while(cnt < machine && j < k){
					if(i > m + job[j].ff) 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)2e5;
	while(l + 1 < r){
		int mid = (l + r)>>1;
		if(good(mid, 0)){
			r = mid;
		}else{
			l = mid;
		}
	}
	cout << r << '\n';
	good(r, 1);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 35 / 100