Submission #467549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
467549	2021-08-23T14:56:33 Z	Ilsiya	Job Scheduling (CEOI12_jobs)	C++17	100 / 100	692 ms	31296 KB

jobs

#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

#	Verdict	Execution time	Memory	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