Submission #415376

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
415376	2021-06-01T03:12:24 Z	HadiHosseini	Job Scheduling (CEOI12_jobs)	C++14	100 / 100	356 ms	21324 KB

jobs

#include <bits/stdc++.h>

using namespace std;

void show(long long cur, vector<pair<int, int>> v, int n, int d, int m) {
	int j = 0;
	for(int day = 1 ; day <= n ; day++){
		long long rev = cur;
		while(j < m && rev && v[j].first <= day){
			if(v[j].first <= day + d){
				cout << v[j].second << " ";
				rev--;
				j++;
			}
		}
		cout << "0\n";
	}
}

bool f(long long cur, vector<pair<int, int>> v, int n, int d, int m) {
	int j = 0;
	for(int day = 1 ; day <= n ; day++){
		long long rev = cur;
		while(j < m && rev && v[j].first <= day){
			if(v[j].first <= day + d && v[j].first >= day - d){
				rev--;
				j++;
			}
			else {
				return false;
			}
		}
	}
	if(j == m) return true;
	return false;
}

long long bs(vector<pair<int, int>> v, int n, int d, int m){
	long long lo = -1; long long hig = 1e5;
	for(long long i = hig - lo; i; i /= 2){
		while(lo + i <= hig && !f(lo + i, v, n, d, m)) lo += i;
	}
	return lo + 1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n, d, m; cin >> n >> d >> m;
	vector<pair<int, int>> v(m);
	for(int i = 1 ; i <= m; i++){
		cin >> v[i - 1].first;
		v[i - 1].second = i;
	}
	sort(v.begin(), v.end());

	long long ans = bs(v, n, d, m);
	cout << ans << "\n";
	show(ans, v, n, d, m);

	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	29 ms	2644 KB	Output is correct
2	Correct	27 ms	2648 KB	Output is correct
3	Correct	31 ms	2636 KB	Output is correct
4	Correct	35 ms	2636 KB	Output is correct
5	Correct	29 ms	2652 KB	Output is correct
6	Correct	27 ms	2636 KB	Output is correct
7	Correct	36 ms	2644 KB	Output is correct
8	Correct	34 ms	2636 KB	Output is correct
9	Correct	40 ms	2688 KB	Output is correct
10	Correct	38 ms	2644 KB	Output is correct
11	Correct	35 ms	2648 KB	Output is correct
12	Correct	70 ms	4952 KB	Output is correct
13	Correct	104 ms	7376 KB	Output is correct
14	Correct	177 ms	9648 KB	Output is correct
15	Correct	189 ms	12064 KB	Output is correct
16	Correct	257 ms	14392 KB	Output is correct
17	Correct	285 ms	16748 KB	Output is correct
18	Correct	317 ms	19016 KB	Output is correct
19	Correct	356 ms	21324 KB	Output is correct
20	Correct	276 ms	16736 KB	Output is correct