oj.uz

답안 #645486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
645486 2022-09-27T08:51:17 Z kalash04 Job Scheduling (CEOI12_jobs) C++17
100 / 100
 243 ms 21964 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define int long long int

bool check(vector<pair<int, int>>& a, int machines, int delay, int n) {
	int left = machines;
	int i = 0;
	for(int day = 1; day <= n; day++) {
		left = machines;
		while(i < a.size() and a[i].first <= day) {
			if(left > 0) {
				if(a[i].first + delay < day) return false;
				left--;
				i++;
			} else {
				break;
			}
		}
	}
	return (i == a.size());
}

void getday(vector<pair<int, int>>& a, int machines, int delay, int n) {
	int left = machines;
	int i = 0;
	for(int day = 1; day <= n; day++) {
		left = machines;
		while(i < a.size() and a[i].first <= day) {
			if(left > 0) {
				cout << a[i].second << " ";
				left--;
				i++;
			} else {
				break;
			}
		}
		cout << "0\n";
	}
}

void solve() {
	int n, d, m;
	cin >> n >> d >> m;
	vector<pair<int, int>> a(m);
	for(int i = 0; i < m; i++) {
		cin >> a[i].first;
		a[i].second = i + 1;
	}
	sort(a.begin(), a.end());
	int l = 0, r = m;
	while(l < r) {
		int mid = l + (r - l) / 2;
		bool flag = check(a, mid, d, n);
		if(flag) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	cout << l << "\n";
	getday(a, l,d, n);
}
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
  cout.tie(NULL);
	solve();
}

Compilation message

jobs.cpp: In function 'bool check(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
jobs.cpp:12:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |   while(i < a.size() and a[i].first <= day) {
      |         ~~^~~~~~~~~~
jobs.cpp:22:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  return (i == a.size());
      |          ~~^~~~~~~~~~~
jobs.cpp: In function 'void getday(std::vector<std::pair<long long int, long long int> >&, long long int, long long int, long long int)':
jobs.cpp:30:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   while(i < a.size() and a[i].first <= day) {
      |         ~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 2640 KB Output is correct
2 Correct 17 ms 2636 KB Output is correct
3 Correct 17 ms 2672 KB Output is correct
4 Correct 17 ms 2544 KB Output is correct
5 Correct 19 ms 2632 KB Output is correct
6 Correct 16 ms 2636 KB Output is correct
7 Correct 16 ms 2644 KB Output is correct
8 Correct 16 ms 2508 KB Output is correct
9 Correct 26 ms 2872 KB Output is correct
10 Correct 26 ms 2772 KB Output is correct
11 Correct 24 ms 2624 KB Output is correct
12 Correct 54 ms 5156 KB Output is correct
13 Correct 74 ms 7428 KB Output is correct
14 Correct 105 ms 10188 KB Output is correct
15 Correct 126 ms 12300 KB Output is correct
16 Correct 155 ms 15200 KB Output is correct
17 Correct 192 ms 17220 KB Output is correct
18 Correct 206 ms 19772 KB Output is correct
19 Correct 243 ms 21964 KB Output is correct
20 Correct 196 ms 17024 KB Output is correct