Submission #415373

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
415373	2021-06-01T03:03:55 Z	HadiHosseini	Job Scheduling (CEOI12_jobs)	C++14	60 / 100	373 ms	21456 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 = 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

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	23 ms	2640 KB	Output isn't correct
2	Incorrect	31 ms	2644 KB	Output isn't correct
3	Incorrect	29 ms	2636 KB	Output isn't correct
4	Incorrect	24 ms	2636 KB	Output isn't correct
5	Incorrect	23 ms	2636 KB	Output isn't correct
6	Incorrect	23 ms	2648 KB	Output isn't correct
7	Incorrect	24 ms	2636 KB	Output isn't correct
8	Incorrect	24 ms	2644 KB	Output isn't correct
9	Correct	48 ms	2676 KB	Output is correct
10	Correct	39 ms	2652 KB	Output is correct
11	Correct	34 ms	2656 KB	Output is correct
12	Correct	70 ms	4944 KB	Output is correct
13	Correct	109 ms	7360 KB	Output is correct
14	Correct	142 ms	9660 KB	Output is correct
15	Correct	179 ms	12228 KB	Output is correct
16	Correct	231 ms	14408 KB	Output is correct
17	Correct	276 ms	16832 KB	Output is correct
18	Correct	298 ms	19112 KB	Output is correct
19	Correct	373 ms	21456 KB	Output is correct
20	Correct	301 ms	16712 KB	Output is correct