Submission #941479

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941479	2024-03-09T01:54:52 Z	leshin	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	334 ms	24548 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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	2776 KB	Output isn't correct
2	Incorrect	26 ms	2776 KB	Output isn't correct
3	Incorrect	26 ms	2688 KB	Output isn't correct
4	Incorrect	26 ms	2776 KB	Output isn't correct
5	Incorrect	26 ms	2824 KB	Output isn't correct
6	Incorrect	26 ms	2764 KB	Output isn't correct
7	Incorrect	26 ms	2768 KB	Output isn't correct
8	Incorrect	26 ms	2696 KB	Output isn't correct
9	Incorrect	135 ms	5408 KB	Output isn't correct
10	Incorrect	147 ms	5508 KB	Output isn't correct
11	Correct	27 ms	2136 KB	Output is correct
12	Correct	31 ms	3664 KB	Output is correct
13	Correct	46 ms	6740 KB	Output is correct
14	Correct	105 ms	8856 KB	Output is correct
15	Correct	85 ms	9916 KB	Output is correct
16	Correct	137 ms	12616 KB	Output is correct
17	Correct	185 ms	15488 KB	Output is correct
18	Incorrect	155 ms	20216 KB	Output isn't correct
19	Incorrect	334 ms	24548 KB	Output isn't correct
20	Correct	143 ms	15764 KB	Output is correct