Submission #940087

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
940087	2024-03-07T05:28:54 Z	leshin	Job Scheduling (CEOI12_jobs)	C++17	40 / 100	275 ms	25180 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	3024 KB	Output isn't correct
2	Incorrect	35 ms	3024 KB	Output isn't correct
3	Incorrect	26 ms	3024 KB	Output isn't correct
4	Incorrect	26 ms	3028 KB	Output isn't correct
5	Incorrect	26 ms	3020 KB	Output isn't correct
6	Incorrect	26 ms	3020 KB	Output isn't correct
7	Incorrect	26 ms	3028 KB	Output isn't correct
8	Incorrect	28 ms	3032 KB	Output isn't correct
9	Incorrect	133 ms	5680 KB	Output isn't correct
10	Incorrect	133 ms	5540 KB	Output isn't correct
11	Correct	17 ms	2396 KB	Output is correct
12	Correct	30 ms	4432 KB	Output is correct
13	Correct	44 ms	7252 KB	Output is correct
14	Correct	85 ms	9400 KB	Output is correct
15	Correct	75 ms	10320 KB	Output is correct
16	Correct	123 ms	13032 KB	Output is correct
17	Correct	159 ms	16308 KB	Output is correct
18	Incorrect	164 ms	20828 KB	Output isn't correct
19	Incorrect	275 ms	25180 KB	Output isn't correct
20	Correct	143 ms	16156 KB	Output is correct