Submission #713896

#	Time	Username	Problem	Language	Result	Execution time	Memory
713896		iskhakkutbilim	Job Scheduling (CEOI12_jobs)	C++14	0 / 100	351 ms	61856 KiB

jobs

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

#define int long long
#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));
	vector<int> ans[n+1];
	function<int(int)> good=[&](int machine){
		int j = 0;
		for(int i = 1;i <= n; i++) ans[i].clear();
		for(int i = 1;i <= n; i++){
			while(ans[i].size() < machine && j < k){
				if(i > m + job[j].ff) return 0;
				ans[i].push_back(job[j].ss+1);
				j++;
			}
			ans[i].push_back(0);
		}
		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)){
			r = mid;
		}else{
			l = mid;
		}
	}
	if(!good(r)){
		cout << "NO" << '\n';
	}
	cout << r << '\n';
	for(int i = 1;i <= n; i++){
		for(int x : ans[i]) cout << x << ' ';
		cout << '\n';
	}
	return 0;
}

Compilation message (stderr)

jobs.cpp:14:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   14 | main(){
      | ^~~~
jobs.cpp: In lambda function:
jobs.cpp:29:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   29 |    while(ans[i].size() < machine && j < k){
      |          ~~~~~~~~~~~~~~^~~~~~~~~

• Subtask 1: 0 / 100