답안 #940087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940087 2024-03-07T05:28:54 Z leshin Job Scheduling (CEOI12_jobs) C++17
40 / 100
275 ms 25180 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 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