Submission #723757

#	Time	Username	Problem	Language	Result	Execution time	Memory
723757		Toxtaq	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	406 ms	31936 KiB

jobs

#include<iostream>
#include<vector>
#include<map>
using namespace std;int n, d, m;
vector<vector<int>>jobs;bool check(int mid, vector<vector<int>>&tempo){	int day = 1, job = 0, current_day = 1;	while(current_day <= n- d){
		for(int i = 0;i < mid;++i){		
			if(day > current_day)break;
			//cout << current_day << " " << day << " " << job << '\n';
			if(current_day-day<=d)tempo[current_day].push_back(jobs[day][job]);
			else{
			//	cout << "$\n";
				  return false;
			}
			job++;
			if(day == n - d&&job ==jobs[n-d].size()){
			//	cout << "£\n";
				return true;
			}
			if(job == jobs[day].size()){day++;job=0;}
			
		}
		current_day++;
		
	}
//	cout << "€\n";
	return false;
}
int main(){
	cin >> n >> d >> m;
	jobs.resize(n+1);
	for(int i = 1;i <= m;++i){
		int a;
		cin >> a;
		jobs[a].push_back(i);
	}
	int l = 1, r = m, ans = m;
	vector<vector<int>>res(n+1);
	while(r>=l){
		int mid = (l+r)>> 1;
		vector<vector<int>>tempo(n+1);	//	cout << "[" << l << ", " << r << "]\n";
		if(check(mid, tempo)){
			res=tempo;
			r = mid - 1;
			ans = min(ans, mid);
		}
		else{
			l = mid + 1;
		}
		
	}
	cout << ans << '\n';
	for(int i = 1;i<=n;++i){
		for(int j : res[i]){
			cout << j << " ";
		}
		cout << "0\n";
	}
}

Compilation message (stderr)

jobs.cpp: In function 'bool check(int, std::vector<std::vector<int> >&)':
jobs.cpp:15:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |    if(day == n - d&&job ==jobs[n-d].size()){
      |                     ~~~~^~~~~~~~~~~~~~~~~~
jobs.cpp:19:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |    if(job == jobs[day].size()){day++;job=0;}
      |       ~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100