oj.uz

Submission #132224

# Submission time Handle Problem Language Result Execution time Memory
132224 2019-07-18T14:07:00 Z amoo_safar Job Scheduling (CEOI12_jobs) C++14
100 / 100
 195 ms 20236 KB 
#include<bits/stdc++.h>
#define pb push_back

using namespace std;

typedef long long ll;

const int Maxn = 1e5 + 10;

vector<int> rec[Maxn], op[Maxn];
int cnt[Maxn];

int n, m, d;

bool check(int c){
	for(int i = 1; i <= n; i++) cnt[i] = rec[i].size();
	int p = 1, done = 0, free, rem;
	for(int i = 1; i <= n; i++){
		p = max(p, i - d);
		free = c;
		while((p <= i) && (free)){
			rem = min(free, cnt[p]);
			free -= rem;
			cnt[p] -= rem;
			done += rem;
			if(cnt[p] == 0) p++;
		}
	}
	return (done == m);
}

void solve(int c){
	int p = 1, free;
	for(int i = 1; i <= n; i++){
		p = max(p, i - d);
		free = c;
		while((p <= i) && (free)){
			if(rec[p].size() == 0){
				p ++;
				continue;
			}
			free --;
			op[i].pb(rec[p].back());
			rec[p].pop_back();
		}
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> d >> m;
	int v;
	for(int i = 1; i <= m; i++){
		cin >> v;
		rec[v].pb(i);
	}
	int l = 0, r = m, mid;
	while(l + 1 < r){
		mid = (l + r) >> 1;
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	solve(r);
	for(int i = 1; i <= n; i++){
		for(auto x : op[i]) cout << x << " ";
		cout << "0\n";
	}
	return 0;
}
/*
8 2 12
1 2 4 2 1 3 5 6 2 3 6 4
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6772 KB Output is correct
2 Correct 25 ms 6772 KB Output is correct
3 Correct 25 ms 6772 KB Output is correct
4 Correct 24 ms 6768 KB Output is correct
5 Correct 25 ms 6772 KB Output is correct
6 Correct 25 ms 6772 KB Output is correct
7 Correct 24 ms 6772 KB Output is correct
8 Correct 25 ms 6772 KB Output is correct
9 Correct 33 ms 7288 KB Output is correct
10 Correct 34 ms 7416 KB Output is correct
11 Correct 26 ms 6648 KB Output is correct
12 Correct 46 ms 8312 KB Output is correct
13 Correct 70 ms 11256 KB Output is correct
14 Correct 111 ms 13048 KB Output is correct
15 Correct 106 ms 13176 KB Output is correct
16 Correct 173 ms 15480 KB Output is correct
17 Correct 191 ms 20088 KB Output is correct
18 Correct 167 ms 19136 KB Output is correct
19 Correct 195 ms 20236 KB Output is correct
20 Correct 190 ms 20096 KB Output is correct