oj.uz

Submission #553188

# Submission time Handle Problem Language Result Execution time Memory
553188 2022-04-25T03:24:28 Z dyc123 Job Scheduling (CEOI12_jobs) C++14
100 / 100
 261 ms 32116 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

#define ii pair<ll, ll>
#define ll long long
#define fi first
#define se second

int n, d, m;
vector<ii> stX(1000001);
vector<int> ans[100001];

bool f(int x) {
	for(int day=1, j=1; day<=m && j<=n; ++day)
		for(int i=1; i<=x && j<=n && stX[j].fi<=day; ++i)
			if (day>stX[j++].fi+d)
				return 0;
	return 1;
}

void trace(int x) {
	for(int day=1, j=1; day<=m && j<=n; ++day)
		for(int i=1; i<=x && j<=n && stX[j].fi<=day; ++i)
			ans[day].push_back(stX[j++].se);
}

int main() {
	cin.tie(0) -> sync_with_stdio(0);
	cout.tie(0);
	
	cin >> m >> d >> n;
	for(int i=1; i<=n; ++i) { 
		cin >> stX[i].fi;
		stX[i].se=i;
	}

	sort(stX.begin()+1, stX.begin()+n+1);
	
	int lb=1, rb=n+1, mb;
	while (lb<rb) {
		mb=(lb+rb)>>1;
		if (f(mb))
			rb=mb;
		else
			lb=mb+1;
	}
	trace(lb);

	cout << lb << '\n';
	for(int i=1; i<=m; ++i) {
		for(int j: ans[i])
			cout << j << ' ';
		cout << "0\n";
	}
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 19656 KB Output is correct
2 Correct 29 ms 19640 KB Output is correct
3 Correct 26 ms 19664 KB Output is correct
4 Correct 25 ms 19752 KB Output is correct
5 Correct 27 ms 19684 KB Output is correct
6 Correct 28 ms 19676 KB Output is correct
7 Correct 28 ms 19756 KB Output is correct
8 Correct 27 ms 19760 KB Output is correct
9 Correct 36 ms 19828 KB Output is correct
10 Correct 36 ms 19852 KB Output is correct
11 Correct 36 ms 19788 KB Output is correct
12 Correct 68 ms 21388 KB Output is correct
13 Correct 95 ms 23464 KB Output is correct
14 Correct 116 ms 25588 KB Output is correct
15 Correct 152 ms 25528 KB Output is correct
16 Correct 169 ms 27972 KB Output is correct
17 Correct 224 ms 31492 KB Output is correct
18 Correct 242 ms 30944 KB Output is correct
19 Correct 261 ms 32116 KB Output is correct
20 Correct 211 ms 31436 KB Output is correct