답안 #941478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
941478 2024-03-09T01:54:02 Z leshin Job Scheduling (CEOI12_jobs) C++17
0 / 100
120 ms 21740 KB
#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]){
      |             ^~~
# 결과 실행 시간 메모리 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