oj.uz

Submission #132223

# Submission time Handle Problem Language Result Execution time Memory
132223 2019-07-18T14:02:50 Z amoo_safar Job Scheduling (CEOI12_jobs) C++14
60 / 100
 206 ms 23672 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 = n, 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
60.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 6128 KB Output isn't correct
2 Incorrect 18 ms 6132 KB Output isn't correct
3 Incorrect 18 ms 6132 KB Output isn't correct
4 Incorrect 18 ms 6132 KB Output isn't correct
5 Incorrect 18 ms 6132 KB Output isn't correct
6 Incorrect 18 ms 6132 KB Output isn't correct
7 Incorrect 18 ms 6128 KB Output isn't correct
8 Incorrect 17 ms 6128 KB Output isn't correct
9 Correct 33 ms 7544 KB Output is correct
10 Correct 34 ms 7672 KB Output is correct
11 Correct 27 ms 7056 KB Output is correct
12 Correct 47 ms 9208 KB Output is correct
13 Correct 70 ms 12408 KB Output is correct
14 Correct 112 ms 14932 KB Output is correct
15 Correct 105 ms 15164 KB Output is correct
16 Correct 165 ms 18552 KB Output is correct
17 Correct 206 ms 23400 KB Output is correct
18 Correct 167 ms 22112 KB Output is correct
19 Correct 195 ms 23672 KB Output is correct
20 Correct 204 ms 23468 KB Output is correct