oj.uz

Submission #483151

# Submission time Handle Problem Language Result Execution time Memory
483151 2021-10-27T23:17:08 Z Zybg Job Scheduling (CEOI12_jobs) C++11
100 / 100
 505 ms 13744 KB 
#include <iostream>
#include <algorithm>
#include <array>
using namespace std;

int n,d,m;
array<int,2> a[1000010];

bool check(int x){
	int i=1,j=1;
	for(;i<=n;i++){
		int cur = 1;
		while(a[j][0]<=i && j<=m && cur<=x){
			if(i-d>a[j][0]) return 0;
			j++,cur++;
		}
	}
	if(j<m) return 0;
	return 1;
}

void calc(int r){
	for(int i=1,j=1;i<=n;i++){
		int cur = 1;
		while(a[j][0]<=i && j<=m && cur<=r){
			cout << a[j][1] << " ";
			j++,cur++;
		}
		cout << 0 << endl;
	}
}

int main(){
	
	cin >> n >> d >> m;
	for(int i=1;i<=m;i++){
		cin >> a[i][0];
		a[i][1] = i;
	}
	sort(a+1,a+m+1);
	int l = 1, r = 1000010;
	while(l<r){
		int mid = (l+r)/2;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	cout << r << endl;
	calc(r);
	
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1612 KB Output is correct
2 Correct 56 ms 1572 KB Output is correct
3 Correct 43 ms 1584 KB Output is correct
4 Correct 41 ms 1580 KB Output is correct
5 Correct 44 ms 1664 KB Output is correct
6 Correct 53 ms 1560 KB Output is correct
7 Correct 41 ms 1572 KB Output is correct
8 Correct 43 ms 1592 KB Output is correct
9 Correct 159 ms 1820 KB Output is correct
10 Correct 176 ms 1976 KB Output is correct
11 Correct 40 ms 1584 KB Output is correct
12 Correct 79 ms 3072 KB Output is correct
13 Correct 153 ms 4556 KB Output is correct
14 Correct 184 ms 6212 KB Output is correct
15 Correct 211 ms 7584 KB Output is correct
16 Correct 262 ms 9028 KB Output is correct
17 Correct 317 ms 10492 KB Output is correct
18 Correct 378 ms 12060 KB Output is correct
19 Correct 505 ms 13744 KB Output is correct
20 Correct 351 ms 10564 KB Output is correct