Submission #941488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941488	2024-03-09T02:10:12 Z	leshin	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	246 ms	18108 KB

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

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	2776 KB	Output is correct
2	Correct	25 ms	2772 KB	Output is correct
3	Correct	25 ms	2824 KB	Output is correct
4	Correct	25 ms	2772 KB	Output is correct
5	Correct	25 ms	2868 KB	Output is correct
6	Correct	26 ms	2772 KB	Output is correct
7	Correct	32 ms	3032 KB	Output is correct
8	Correct	32 ms	2776 KB	Output is correct
9	Correct	125 ms	4676 KB	Output is correct
10	Correct	133 ms	4720 KB	Output is correct
11	Correct	16 ms	2136 KB	Output is correct
12	Correct	31 ms	3664 KB	Output is correct
13	Correct	45 ms	6740 KB	Output is correct
14	Correct	87 ms	8760 KB	Output is correct
15	Correct	74 ms	9812 KB	Output is correct
16	Correct	126 ms	12488 KB	Output is correct
17	Correct	134 ms	15440 KB	Output is correct
18	Correct	131 ms	14932 KB	Output is correct
19	Correct	246 ms	18108 KB	Output is correct
20	Correct	135 ms	15440 KB	Output is correct