Submission #941488

#	Time	Username	Problem	Language	Result	Execution time	Memory
941488		leshin	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	246 ms	18108 KiB

jobs

#include <bits/stdc++.h>
#include <cmath>
using namespace std;
using ll = long long;

bool check(ll m, const vector<vector<ll>> &requests, ll N, ll D, ll M){
	deque<ll> tasks;
	
	for (ll i = 0; i < N; i++){
		
		for (auto val: requests[i]){
			tasks.push_back(i);
		}
		/*
		for (auto val: tasks){
			cout << val << " ";
		} cout << endl;
		*/

		for (ll j = 0; j < m; j++){
			if (tasks.empty()){
				break;
			} else {

				if (tasks.front() + D < i){
					//cout << "failed" << endl;
					return false;
				}
				tasks.pop_front();
			}
		}
	}
	if (!tasks.empty()){
		return false;
	}
	return true;
	
	//return m < 9;
}

void checks(ll m, const vector<vector<ll>> &requests, ll N, ll D, ll M){
	deque<ll> tasks;
	
	for (ll i = 0; i < N; i++){

		for (auto val: requests[i]){
			tasks.push_back(val);
		}

		for (ll j = 0; j < m; j++){
			if (tasks.empty()){
				break;
			} else {

				cout << tasks.front() + 1 << " ";
				tasks.pop_front();
			}
		}
		cout << 0 << endl;
	}
	
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	ll N, D, M;
	cin >> N >> D >> M;

	vector<vector<ll>> requests(N);
	for (ll i = 0; i < M; i++){
		ll val;
		cin >> val;
		val--;
		requests[val].push_back(i);
	}

	ll l = 1, r = M;

	
	while (l < r){
		ll m = (l + r) / 2;
		if (check(m, requests, N, D, M)){
			r = m;
		} else {
			l = m + 1;
		}
	}


	cout << r << endl;
	checks(r, requests, N, D, M);


}

Compilation message (stderr)

jobs.cpp: In function 'bool check(ll, const std::vector<std::vector<long long int> >&, ll, ll, ll)':
jobs.cpp:11:13: warning: unused variable 'val' [-Wunused-variable]
   11 |   for (auto val: requests[i]){
      |             ^~~

• Subtask 1: 100 / 100