oj.uz

답안 #467549

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467549 2021-08-23T14:56:33 Z Ilsiya Job Scheduling (CEOI12_jobs) C++17
100 / 100
 692 ms 31296 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef long double ld;
#define F first
#define S second

ll n, d, m;
pair<ll, ll> jobs[1000000];

bool cmp(pair<ll, ll> i, pair<ll, ll> j) {
	if (i.F == j.F) return i.S < j.S;
	else return i.F < j.F;  
}

bool f(ll x) {
	ll numb = 0;
	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j < x; j++) {
			if (jobs[numb].F > i) {
				break;
			}
			if (jobs[numb].F + d >= i) {
				numb++;
			}
			else {
				return false;
			}
			if (numb + 1 == m) {
				return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> n >> d >> m;
	for (ll i = 0; i < m; i++) {
		cin >> jobs[i].F;
		jobs[i].S = i + 1;
	}
	sort(jobs, jobs + m);
	ll start = 0, end = m, mid = 0;
	while (start + 1 < end) {
		mid = (start + end) / 2;
		if (f(mid)) {
			end = mid;
		}
		else {
			start = mid;
		}
	}
	cout << end << "\n";
	vll ans[n];
	ll p1 = 0;
	for (ll i = 1; i <= n; i++) {
		for (ll j = 0; j < end; j++) {
			if (jobs[p1].F > i) {
				break;
			}
			if (jobs[p1].F + d >= i) {
				ans[i - 1].push_back(jobs[p1].S);
				p1++;
			}
		}
	}
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < ans[i].size(); j++) {
			cout << ans[i][j] << " ";
		}
		cout << "0" << "\n";
	}
}

Compilation message

jobs.cpp: In function 'int main()':
jobs.cpp:70:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (ll j = 0; j < ans[i].size(); j++) {
      |                  ~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 573 ms 3516 KB Output is correct
2 Correct 568 ms 3520 KB Output is correct
3 Correct 579 ms 3540 KB Output is correct
4 Correct 612 ms 3556 KB Output is correct
5 Correct 566 ms 3516 KB Output is correct
6 Correct 590 ms 3628 KB Output is correct
7 Correct 692 ms 3520 KB Output is correct
8 Correct 654 ms 3516 KB Output is correct
9 Correct 554 ms 5872 KB Output is correct
10 Correct 570 ms 5880 KB Output is correct
11 Correct 54 ms 3396 KB Output is correct
12 Correct 106 ms 6684 KB Output is correct
13 Correct 159 ms 10936 KB Output is correct
14 Correct 248 ms 14660 KB Output is correct
15 Correct 301 ms 15456 KB Output is correct
16 Correct 328 ms 19108 KB Output is correct
17 Correct 390 ms 26200 KB Output is correct
18 Correct 453 ms 26728 KB Output is correct
19 Correct 595 ms 31296 KB Output is correct
20 Correct 383 ms 26196 KB Output is correct