oj.uz

Submission #522396

# Submission time Handle Problem Language Result Execution time Memory
522396 2022-02-04T19:36:58 Z Yazan_Alattar Job Scheduling (CEOI12_jobs) C++14
100 / 100
 494 ms 14344 KB 
#include <bits/stdc++.h>

using namespace std;
const int M = 1000005;
#define F first
#define S second

int n, d, m;
pair <int,int> a[M];

bool check(int mid)
{
	int pos = 1;
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= mid && pos <= m && a[pos].F <= i; ++j) if(i - a[pos++].F > d) return 0;
	return (pos == m + 1);
}

int main()
{
	cin >> n >> d >> m;
	for(int i = 1; i <= m; ++i) cin >> a[i].F, a[i].S = i;
	sort(a + 1, a + m + 1);
	int l = 1, r = m + 1;
	while(l < r){
		int mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << r << endl;
	int pos = 1;
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= r && pos <= m && a[pos].F <= i; ++j, ++pos) cout << a[pos].S << " ";
		cout << 0 << endl;
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1968 KB Output is correct
2 Correct 39 ms 1860 KB Output is correct
3 Correct 38 ms 1904 KB Output is correct
4 Correct 38 ms 1960 KB Output is correct
5 Correct 42 ms 1912 KB Output is correct
6 Correct 46 ms 1860 KB Output is correct
7 Correct 38 ms 1916 KB Output is correct
8 Correct 38 ms 1964 KB Output is correct
9 Correct 149 ms 2052 KB Output is correct
10 Correct 161 ms 2116 KB Output is correct
11 Correct 39 ms 1988 KB Output is correct
12 Correct 77 ms 3704 KB Output is correct
13 Correct 116 ms 5204 KB Output is correct
14 Correct 221 ms 6716 KB Output is correct
15 Correct 198 ms 8140 KB Output is correct
16 Correct 268 ms 9808 KB Output is correct
17 Correct 317 ms 11260 KB Output is correct
18 Correct 335 ms 12588 KB Output is correct
19 Correct 494 ms 14344 KB Output is correct
20 Correct 300 ms 11128 KB Output is correct