oj.uz

Submission #132242

# Submission time Handle Problem Language Result Execution time Memory
132242 2019-07-18T14:50:05 Z Atalasion Job Scheduling (CEOI12_jobs) C++14
100 / 100
 946 ms 21116 KB 
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()
#define F first 
#define S second

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
typedef string str;

const ll MOD = 1e9 + 7;
const ll N = 1e6 + 10;
const ll INF = 1e18;

ll n, d, m;

pll a[N];

bool isval(ll x){
	queue <pll> q;
	ll pnt = 1;
	//cout << x << '\n';
	for (int i = 1; i <= n; i++){
		if (pnt != m + 1){
			while ((pnt != m + 1) && (a[pnt].F == i)) q.push(a[pnt]), pnt ++;
		}
		//cout << i << ' ' << pnt << ' ' << q.size() << ' ' << x << ' ';
		for (int j = 0; j < x; j++){
		    if (q.size() == 0) break;
		    q.pop();
		}
		//cout << q.size() << '\n';
		if (q.size() != 0){
			if (q.front().F + d < i + 1){
				return 0;
			}
		}
	}
	if (q.size()) return 0;
	return 1;
}


int main(){
	cin >> n >> d >> m;
	for (int i = 1; i <= m; i++){
		ll v;
		cin >> v;
		a[i] = {v, i};
	}
	sort(a + 1, a + m + 1);
	ll l = 0, r = INF;
	while (r - l > 1){
		ll mid = (l + r) / 2;
		//cout << l << ' ' << r << '\n';
		if (isval(mid)) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	ll x = r;
	queue <pll> q;
	ll pnt = 1;
	for (int i = 1; i <= n; i++){
		if (pnt != m + 1){
			while ((pnt != m + 1) && (a[pnt].F == i)) q.push(a[pnt]), pnt ++;
		}
		//cout << i << ' ' << pnt << ' ' << q.size() << ' ' << x << ' ';
		for (int j = 0; j < x; j++){
		    if (q.size() == 0) break;
			cout << q.front().S << ' ';
		    q.pop();
		}
		cout << 0 << '\n';
		//cout << q.size() << '\n';
		if (q.size() != 0){
			if (q.front().F + d < i + 1){
				return 0;
			}
		}
	}
	
	
	
	
	
	
	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 142 ms 4152 KB Output is correct
2 Correct 145 ms 4136 KB Output is correct
3 Correct 139 ms 4136 KB Output is correct
4 Correct 138 ms 4136 KB Output is correct
5 Correct 143 ms 4152 KB Output is correct
6 Correct 139 ms 4280 KB Output is correct
7 Correct 142 ms 4152 KB Output is correct
8 Correct 141 ms 4168 KB Output is correct
9 Correct 122 ms 2824 KB Output is correct
10 Correct 124 ms 2844 KB Output is correct
11 Correct 103 ms 2544 KB Output is correct
12 Correct 205 ms 5112 KB Output is correct
13 Correct 299 ms 7132 KB Output is correct
14 Correct 465 ms 10036 KB Output is correct
15 Correct 496 ms 11768 KB Output is correct
16 Correct 716 ms 13944 KB Output is correct
17 Correct 806 ms 16376 KB Output is correct
18 Correct 831 ms 18532 KB Output is correct
19 Correct 946 ms 21116 KB Output is correct
20 Correct 804 ms 16192 KB Output is correct