Submission #415369

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
415369	2021-06-01T02:57:02 Z	HadiHosseini	Job Scheduling (CEOI12_jobs)	C++14	40 / 100	357 ms	24868 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){
				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 = n;
	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

40.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	26 ms	2884 KB	Output isn't correct
2	Incorrect	26 ms	2940 KB	Output isn't correct
3	Incorrect	27 ms	2892 KB	Output isn't correct
4	Incorrect	26 ms	2892 KB	Output isn't correct
5	Incorrect	27 ms	2880 KB	Output isn't correct
6	Incorrect	26 ms	2932 KB	Output isn't correct
7	Incorrect	26 ms	2952 KB	Output isn't correct
8	Incorrect	27 ms	2892 KB	Output isn't correct
9	Incorrect	40 ms	2928 KB	Output isn't correct
10	Incorrect	46 ms	2908 KB	Output isn't correct
11	Correct	34 ms	3032 KB	Output is correct
12	Correct	66 ms	5700 KB	Output is correct
13	Correct	104 ms	8408 KB	Output is correct
14	Correct	170 ms	11564 KB	Output is correct
15	Correct	176 ms	13944 KB	Output is correct
16	Correct	248 ms	17328 KB	Output is correct
17	Correct	264 ms	20056 KB	Output is correct
18	Incorrect	299 ms	22192 KB	Output isn't correct
19	Incorrect	357 ms	24868 KB	Output isn't correct
20	Correct	306 ms	20048 KB	Output is correct