Submission #941478

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
941478	2024-03-09T01:54:02 Z	leshin	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	120 ms	21740 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	12 ms	2520 KB	Output isn't correct
2	Incorrect	10 ms	2608 KB	Output isn't correct
3	Incorrect	12 ms	2520 KB	Output isn't correct
4	Incorrect	11 ms	2516 KB	Output isn't correct
5	Incorrect	11 ms	2460 KB	Output isn't correct
6	Incorrect	11 ms	2520 KB	Output isn't correct
7	Incorrect	12 ms	2480 KB	Output isn't correct
8	Incorrect	12 ms	2520 KB	Output isn't correct
9	Incorrect	15 ms	4908 KB	Output isn't correct
10	Incorrect	16 ms	4960 KB	Output isn't correct
11	Incorrect	11 ms	1880 KB	Unexpected end of file - int32 expected
12	Incorrect	23 ms	3164 KB	Unexpected end of file - int32 expected
13	Incorrect	30 ms	5976 KB	Unexpected end of file - int32 expected
14	Incorrect	54 ms	9044 KB	Unexpected end of file - int32 expected
15	Incorrect	52 ms	8284 KB	Unexpected end of file - int32 expected
16	Incorrect	100 ms	12268 KB	Unexpected end of file - int32 expected
17	Incorrect	101 ms	15440 KB	Unexpected end of file - int32 expected
18	Incorrect	91 ms	17920 KB	Output isn't correct
19	Incorrect	120 ms	21740 KB	Output isn't correct
20	Incorrect	90 ms	15396 KB	Unexpected end of file - int32 expected